[백준] 1806번: 부분합 (c++)

 

문제

---

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

 

1806번: 부분합

 

문제조건

---

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

 

풀이

---

투포인터 알고리즘의 대표적인 예시 문제이다. 투포인터 알고리즘은 시간복잡도가 O(n)임으로 이번 문제처럼 효율성을 생각해야 하는 문제에서 사용하기 적절하다(이중 for문시 시간복잡도 O(\(n^2\))으로 시간초과)

코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n, s;
	cin >> n >> s;
	vector<int> arr(n);

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	int start = 0, end = 0, sum = 0, minLen = 100001;
	while (start <= end) {
		if (sum >= s) {	
			minLen = min(minLen, end - start);	
			sum -= arr[start++];
		}
		else if (end == n) break;
		else sum += arr[end++];	
	}

	if (minLen == 100001) cout << 0;
	else cout << minLen;

	return 0;
}