[C++] BOJ / 1806번 / 부분합

1806번: 부분합

 

문제

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

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

10 15
5 1 3 5 10 7 4 9 2 8

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

2

풀이

시간초과를 피하기 위해 두 개의 포인터를 사용하여 수열을 탐색하면서 합이 S 이상인 연속된 수들의 부분합 중 가장 짧은 것의 길이를 구하는 문제입니다.

---

#include<iostream>

#define MAX 100000

using namespace std;

int n, s;
int num[MAX];
int ans = MAX;

void input()
{
	cin >> n >> s;
	for (int i = 0; i < n; ++i)
		cin >> num[i];
}

void solve()
{
	int sum = 0, left = 0, right = 0;

	while (right <= n)
	{
		if (sum >= s)
		{
			ans = min(ans, right - left);
			sum -= num[left++];
		}
		else
			sum += num[right++];
	}
}

void init()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

int main()
{
	init();
	input();
	solve();

	if (ans == MAX) cout << 0 << '\n';
	else cout << ans << '\n';

	return 0;
}