[백준 1806 | C++] 부분합 :: 투 포인터

• 문제 링크 : 1806번: 부분합
• 문제 태그 : 누적 합, 투 포인터 

 

풀이

태그 그대로 누적합과 투포인터 개념을 이용했습니다...

 

문제 조건으로 N이 10^5 이하이기 때문에 누적합 배열을 이중 for문으로 탐색할 시 시간초과 판정을 받습니다. 따라서 선형 시간 내에 해결해야 했고 이를 위한 알고리즘으로 투 포인터를 떠올렸습니다.😎

 

누적합 배열의 경우 (당연히) 오름차순 배열이기 때문에, right 포인터를 오른쪽으로 움직이는 것은 구간의 합이 커지고 left포인터를 오른쪽으로 움직이는 것은 구간의 합이 작아진다는 것을 의미합니다. 

 

따라서 sum[r] - sum[l],구간의 합이 기준값 s보다 크거나 작을 때 경우를 나누어서 포인터를 움직였습니다. 

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;
const int INF = 1 << 30;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, s;
	cin >> n >> s;
	vector<int>v(n + 1, 0);
	vector<int>sum(n + 1, 0);
	for (int i = 1;i <= n;i++) cin >> v[i];

	for (int i = 1;i <= n;i++) {
		sum[i] = sum[i - 1] + v[i];
	}

	int res = INF;
	int l = 0;
	int r = 1;
	while ((l <= r) && l <= n && r <=n) {
		int tmp = INF;

		if (sum[r] - sum[l] >= s) {
			tmp = r - l;
			l++;
		}
		else {
			r++;
		}

		if (tmp < res) {
			res = tmp;
		}
	}

	if (res == INF) cout << 0;
	else cout << res;
}