[C/C++] 백준 - 1806번 : 부분합

https://www.acmicpc.net/problem/1806

1806번: 부분합

문제

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

 

투포인터로 범위를 넓혀가는 방식으로 구현해야한다. 단, 원소 하나로 S보다 크거나 같은 조건을 충족할 수 있기 때문에 시작할 때는 두 좌표 모두 0으로 시작해야한다.

#include <iostream>

using namespace std;

int N, S;
vector<int> ps;

void input() {
	cin >> N >> S;
	ps = vector<int>(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> ps[i];
	}
}

int solution() {
	int pl = 0, pr = 0;

	int answer = INF;
	int total = ps[pl];
	while (pl <= pr) {
		if (total < S) {
			pr++;
			if (pr == N) break;
			total += ps[pr];
		}
		else {
			answer = min(answer, pr - pl + 1);
			total -= ps[pl];
			pl++;
		}
	}

	return answer == INF ? 0 : answer;
}

int main() {
	fastio;
	input();	
	cout << solution();

	return 0;
}