백준 1806번, 부분합 풀이

문제

백준 1806번

풀이

투포인터, 누적합(map), 분할정복을 사용하여 풀 수 있습니다.

이 문제의 경우 배열의 모든 원소가 자연수이므로 투포인터 풀이도 가능합니다.

 

왼쪽(l), 오른쪽(r) 변수와 l ~ r 사이의 합을 저장하는 sum 변수를 만들어 문제의 조건에 맞게 l과 r을 관리하면 됩니다.

 * sum이 S(문제에서 주어지는 것)보다 크거나 같으면 left를 한칸 오른쪽으로 옮깁니다.

 * 그렇지 않으면 right를 오른쪽으로 옮깁니다.

- 위 과정을 l과 r 모두 n - 1이 될 때까지 반복합니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);

	int n, s, ans = 1e9;
	cin >> n >> s;
	vector<int> arr(n);

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

	int l = 0, r = 0, sum = arr[0];
	while (l <= n && r <= n) {
		if (sum >= s) ans = min(ans, r - l + 1);

		if (sum < s) {
			r++;
			if (r >= n) break;
			sum += arr[r];
		} else {
			if (++l >= r) {
				if (l >= n) break;
				r = l;
				sum = arr[r];
			} else {
				sum -= arr[l - 1];
			}
		}
	}

	cout << (ans == 1e9 ? 0 : ans);
}