-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
[3-4]연속 부분수열 오답 질문드립니다..
23.01.20 10:35 작성 23.01.20 10:36 수정 조회수 211
0
[3-4] 연속 부분수열 이제 공부를 시작한지 얼마안된 코린이입니다.. 어디가 잘못되었는지 모르겠어요.. 케이스 3,5 에서 리턴값 1차이로 틀리네요..
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int lt = 0, rt = 0, sum = 0, answer = 0;
int count = sc.nextInt();
int target = sc.nextInt();
int[] arr = new int[count];
for (int i = 0; i < count; i++) {
arr[i] = sc.nextInt();
}
while (rt < count) {
if (sum == target) {
answer++;
sum -= arr[lt++];
} else if (sum < target) {
sum += arr[rt++];
} else {
sum -= arr[lt++];
}
}
while(lt < count) {
sum -= arr[lt++];
if(sum == target) {
answer++;
}
if(sum < target) break;
}
System.out.println(answer);
}
}
답변을 작성해보세요.
0
김태원
지식공유자2023.01.21
안녕하세요^^
위에 코드는 다음과 같은 입력이라면
5 3
1 1 1 1 1
수열의 끝부분 3개의 합이 3이 되는 경우를 카운트하지 못합니다.
첫 번째 while(rt < count) 문이 끝나면
if(sum == target) answer++;
해주면 해결됩니다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int lt = 0, rt = 0, sum = 0, answer = 0;
int count = sc.nextInt();
int target = sc.nextInt();
int[] arr = new int[count];
for (int i = 0; i < count; i++) {
arr[i] = sc.nextInt();
}
while (rt < count) {
if (sum == target) {
answer++;
sum -= arr[lt++];
} else if (sum < target) {
sum += arr[rt++];
} else {
sum -= arr[lt++];
}
}
if(sum == target) answer++;
while(lt < count) {
sum -= arr[lt++];
if(sum == target) {
answer++;
}
if(sum < target) break;
}
System.out.println(answer);
}
}
답변 1