백준 [1806] "부분 합"

문제를 보자마자 브루트포스를 이용해 풀이하면 무조건 시간 초과가 날 것이라는 것을 직감하고 DP와 같은 방식으로 접근하고자 했지만 "연속된" 수를 사용한다는 것에서 DP를 사용하는 것이 큰 의미가 없을거 같다는 생각이 들었다. 결국 START, END 포인터를 이용해 투 포인터 문제로 생각했다. 하지만 간단한 투포인터 문제만 풀어본 기억이 있어 결국 시간 초과가 났고 풀이를 찾아봤다.

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

using namespace std;

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

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

	int start = 0;
	int end = 0;
	int cnt = 100000000;
	int sum = 0;

	while (start <= end) {
		if (sum >= s) {
			cnt = min(cnt, end - start);
			sum -= v[start];
			start++;
		}
		else if (end == n) break;
		else {
			sum += v[end++];
		}
	}

	if (cnt == 100000000)
		cout << 0;
	else {
		cout << cnt;
	}

	return 0;
}