[BOJ] 1806번: 부분합 (C++)

Problem

1806번: 부분합

---

Solution

구간 합의 시작을 가리키는 start 포인터와 끝을 가리키는 end 포인터를 두고 조건에 맞게 end 포인터와 start 포인터를 증가시키면 된다.

 

처음부터 숫자를 하나씩 더해가면서 합이 S 이상이 되면 start 포인터를 1 증가시키고 합을 갱신한다.

 

갱신된 합이 S보다 작으면 end 포인터를 합이 S 이상이 될 때까지 증가시킨다.

 

이 과정을 반복하는 동안 end - start의 값을 계산하여 가장 짧은 부분합의 길이를 구한다.

#include <cstdio>
#include <vector>

using namespace std;

int main() {
	int N, S;
	scanf("%d%d", &N, &S);

	vector<int> arr(N);
	for(int i=0; i<N; i++) scanf("%d", &arr[i]);

	int end = 0, sum = 0; 
	int len = 0, minlen = 100001;
	// 처음부터 숫자를 하나씩 더해가면서
	// 합이 S 이상이 되면 start 포인터를 1 증가시키고 합을 갱신한다.
	// 갱신된 합이 S보다 작으면 end 포인터를 합이 S 이상이 될때까지 증가시킨다.
	// 이 과정을 반복하는 동안 end - start의 값을 계산하여 최솟값을 찾는다.
	for(int start=0; start<N; start++) {
		// end가 start보다 크거나 같게 조정한다
		end = end >= start ? end : start;
		for(; end<N; end++) {
			if(sum >= S) break;
			sum += arr[end];
			len += 1;
		}

		if(sum < S) {
			sum -= arr[start];
			len--;
			continue;
		}
		minlen = min(minlen, len);
		sum -= arr[start];
		len--;
	}

	printf("%d\n", minlen == 100001 ? 0 : minlen);
}

 

---

Result