백준 [1806] 부분합

www.acmicpc.net/problem/2003의 응용 문제

사실 응용문제랄 것도 없이 if문 하나만 추가해주면 끝난다.

 

여기서 주의할 점은 부분합이 S 이상을 찾는 것이다.

부분합이 S인 경우만 찾으면 안 된다.

 

생각보다 간단하다.

합이 S 이상인 경우, 시작점과 마지막 점의 차이를 구한 후,

이 차이가 최소값이지만 판별해주면 된다.

 

 

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

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N, S, data, MINLEN = 0x7FFFFFFF;
	int start = 0, end = 0, sum = 0;
	vector<int> v;
	cin >> N >> S;
	for (int i = 0; i < N; i++)
	{
		cin >> data;
		v.push_back(data);
	}
	v.push_back(0); // 벡터로 할 시, 뒤에 0 추가 안 해주면 런타임 에러발생
	while (end<=N)
	{
		if (sum >= S)
		{
			int temp = end - start;
			if (temp < MINLEN)
				MINLEN = temp;
			sum -= v[start];
			start++;
		}
		else
		{
			sum += v[end];
			end++;
		}
	}
	if (MINLEN == 0x7FFFFFFF)
		cout << 0;
	else
		cout << MINLEN;
	return 0;
}