사용한 것
- 연속된 구간의 합들을 효율적으로 계산하기 위한 구간합
풀이 방법
- 구간합을 이용하여 O(n)으로 풀이한다.
arr
의 i 번째 인덱스에 i 번째 인덱스 까지의 합을 저장한다.
l
을 -1 부터 r
을 0 부터 시작하여 while 문을 수행한다.
- arr[r] - arr[l]의 값이
S
보다 작으면 r 증가 (l == -1이면 0으로)
- arr[r] - arr[l]의 값이
S
이상이면 answer
교체 후 l or r 증가 (l 증가하면 r과 같아지는 경우는 r 증가)
코드
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
int N = Integer.parseInt(line[0]);
int S = Integer.parseInt(line[1]);
int[] arr = new int[N];
line = br.readLine().split(" ");
int sum = 0;
for (int i = 0; i < N; i++) {
sum += Integer.parseInt(line[i]);
arr[i] = sum;
}
int l = -1;
int r = 0;
int answer = N + 1;
while (r < N) {
int num1 = l == -1 ? 0 : arr[l];
int num2 = arr[r];
int diff = num2 - num1;
if (diff < S) {
r++;
} else {
answer = Math.min(r - l, answer);
if (l + 1 == r) {
r++;
} else {
l++;
}
}
}
System.out.println(answer == N + 1 ? 0 : answer);
}
}