문제
풀이
S이상인 부분합 중 가장 배열의 크기가 작은 값을 출력하는 문제이다. start와 end사이의 모든 값을 다 더하도록 설정한다. start, end를 0으로 시작하여, start가 end를 넘겼을 때, end가 N을 넘겼을 때 while문은 종료된다. while문 안에서는 sum이 S보다 작다면, end를 늘려 값을 추가하여 sum을 늘리도록 한다. result는 S를 넘는 부분합을 가지는 배열의 최소 크기라고 정의한다. sum이 S보다 크다면 result와 start와 end사이의 거리 중 작은 값을 result로 설정한다. 그 이후, start를 키워 부분 배열의 크기를 줄여 조건을 만족시키는지 확인한다. sum이 s라면 result와 start와 end 사이의 거리를 비교한다. 또한, end를 늘려 다른 부분 배열의 가능성을 확인한다. (start를 늘려 다른 부분 배열의 가능성을 확인해도 된다.)
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, S;
vector<int> testcase;
int main(){
scanf("%d %d", &N, &S);
for(int i = 0; i<N; i++){
int input;
scanf("%d", &input);
testcase.push_back(input);
}
int start = 0;
int end = 0;
int sum = testcase[0];
int result = N+1;
while(start <= end && end < N){
if(sum < S){
end++;
sum += testcase[end];
}
else if(sum > S){
result = min(result, end - start + 1);
sum -= testcase[start];
start++;
}
else if(sum == S){
result = min(result, end - start + 1);
end++;
sum += testcase[end];
}
}
if(result == N+1){
printf("0\n");
}
else printf("%d\n", result);
}
