[백준] 1806번. 부분합 (C++)

[문제]

www.acmicpc.net/problem/1806

1806번: 부분합

 

[풀이]

연속된 구간의 부분합을 구하는 문제이므로 투포인터 알고리즘을 사용해서 풀었다.

(투포인터 알고리즘 : https://tnwlswkd.tistory.com/44 )

 

 

start부터 end까지의 부분합이 S 이상인 경우 구간의 길이를 구하고 start를 한 칸 뒤로 움직여서 구간의 길이를 좁힌다.

이 때 start와 end가 같다면 최소 구간이 되므로 1을 출력하고 끝낸다.

 

부분합이 S 미만인 경우 end를 한 칸 뒤로 움직여서 구간의 길이를 넓힌다.

 

[코드]

 

시간 : 32ms

 

#include <iostream>
#include <vector>
#define MAX 100000

using namespace std;

int N,S;
int res = 1e9;
int sequence[MAX] = { 0, };

int main(void)
{
	cin >> N >> S;
	for (int i = 0; i < N; i++)		cin >> sequence[i];

	int start = 0;
	int end = 0;
	int total = sequence[0];

	while (end < N) {
		if (total < S)
		{
			end++;
			total += sequence[end];
		}
		else {
			if (start == end)
			{
				cout << "1";
				return 0;
			}
			int len = end - start + 1;
			if (len < res)		res = len;
			total -= sequence[start];
			start++;
		}
	}
	if (res == 1e9)	cout << "0";
	else    cout << res;
	return 0;
}