C++ / 백준 / 1806 / 부분합

문제

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

1806번: 부분합

문제풀이

이런 식으로 sum값이 목푯값보다 작다면 sum+=arr[idx2]을 하고 idx2를 한 칸 오른쪽으로,

sum값이 목푯값 이상이라면 answer값에 answer값과 idx2-idx2+1의 값 중 더 작은 값을 저장한다.

그다음, sum-=arr[idx]을 하고 idx를 한 칸 오른쪽으로 옮긴다.

처음에 배열을 N크기가 아닌 N+1만큼 사이즈로 생성하는 이유는 idx2가 N일 때 바로 끝내면 경우의 수중 몇 개를 생략하므로 idx2가 N일 때 값이 부족하여 idx2를 +1 하는 순간 끝내도록 하기 위함이다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N(0), S(0);	
	cin >> N >> S;

	int idx(0),idx2(0);	

	vector<int>seq(N + 1, 0);
	for (idx = 0; idx < N; ++idx)
		cin >> seq[idx];

	idx = 0;
	int sum(0);
	int answer(100001);

	while (idx2 < seq.size()) {
		if (sum >= S) {
			answer = min(answer, idx2 - idx);
			sum -= seq[idx];
			++idx;
		}
		else if (sum < S) {
			sum += seq[idx2];
			++idx2;
		}
	}
	if (answer == 100001) answer = 0;
	cout << answer;
}