[1806] 부분합

www.acmicpc.net/problem/1806

1806번: 부분합

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

풀이

'투 포인터' 알고리즘을 이용하기 위해 left, right 변수를 초기화 값으로 각각 0으로 두고 시작한다.

 다른 투포인터 알고리즘을 이용한 문제와 비슷하게 while문 안에서 right가 위치해있는 값을 sum에 합하면서 진행한다.

그리고 만약 현재 left부터 right까지의 합이 입력 받은 S보다 크다면, 해당 left와 right사이의 길이와 min_len의 값을 비교해서 더 작은 값을 min_len에 저장한다.

right가 n까지 도달하면 break를 하여 while문을 빠져나오고 min_len의 값을 출력하고 마무리 된다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int N, S, left = 0, right = 0, cnt = 0, sum = 0, min_len = 216000000;
	cin >> N >> S;
	vector<int> vec(N);

	for (int i = 0; i < N; i++)
		cin >> vec[i];

	while (1) {
		if (sum >= S) {
			min_len = min(min_len, right - left);
			sum -= vec[left++];
		}
		else if (right == N)
			break;
		else {
			sum += vec[right++];
		}
	}

	if (min_len >= 216000000)
		cout << "0";
	else
		cout << min_len;

	return 0;
}