BOJ_1806 부분합(C++)

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

1806번: 부분합

부분합 문제입니다. 

0.5초의 제한시간을 가지고 있어 선형시간을 가지는 알고리즘을 생각했습니다.

주어진 예제에서 시뮬레이션 아이디어는 다음과 같습니다.

 

파란색 화살표에서는 S이상의 부분합을 찾은 상황으로써, start 인덱스를 증가시킬 수 있다면(증가시켜도 S이상이라면) 증가시키고 그럴수 없다면 last 인덱스를 증가시켜가며 최단 길이를 찾습니다.

빨간 화살표에서는 파란색 화살표에서 정해진 last 인덱스를 기준으로 최단 길이를 찾고, 지금까지 중 최단 거리를 비교해서 최소값을 저장합니다.

검은색 화살표는 이후 last 인덱스가 입력 N을 넘어가며 종료됩니다.

 

위의 경우 가장 짧은 길이인 2가 출력됩니다.

 

이를 코드로 구현하면 다음과 같습니다.

// BOJ_1806
// 2212KB, 8ms
#include <iostream>
#include <algorithm>

using namespace std;

int N, S;
short NS[100000];
int answer = INT32_MAX;

int main()
{
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);

	// 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다.
	cin >> N >> S;

	// 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
	for (int i = 0; i < N; i++)
		cin >> NS[i];

	// 첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.
	int sum = NS[0];
	int start = 0, last = 0;
	while(last < N)
	{
		// 부분 수열의 합이 S이상이 됐으면
		if (sum >= S)
		{
			// start 인텍스를 증가시켜가면서 가능한 짧은 수열을 만든다.
			while (sum - NS[start] >= S)
			{
				sum = sum - NS[start];
				start++;
			}
			// last 인덱스가 정해져있을 때 가장 짧은 길이
			answer = min(answer, last - start + 1);
		}

		// 부분 수열의 합이 S이상이 될때까지 last인덱스를 증가시킨다.
		last++;
		sum += NS[last];
	}

	// 첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.
	if (answer != INT32_MAX)
		cout << answer;
	else
		cout << 0;

	return 0;
}