[BOJ] 1806 : Subsequence - travelbeeee

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

---

[ 알고리즘풀이 ]

 Two-Pointer를 이용해 배열을 한 번 순회하면서 S보다 크거나 같은 가장 작은 구간을 찾을 수 있다.

1. list 배열을 Pointer( j ), Pointer( i ) 를 이용해 앞에서부터 순회하며 구간의 합을 구한다.

  ( 이때, j 는 시작점 i 는 끝점을 의미한다. )

2. 끝점인 i 를 올려가며 배열을 순회하다 Sum이 S보다 크거나 같아지는 순간( 즉,  j ~ i 까지의 합이 S보다 크거나 같아졌다 ), j ~ i 까지의 합이 여전히 S보다 큰 시점까지 시작점인 j 도 올린다. 그러면 현재 상태에서의 최소 길이가 만들어지므로 답을 갱신하면 된다.

#include<iostream>
#include<algorithm>
#define INF 987654321

using namespace std;

int N, S, list[100000] = {};

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

	cin >> N >> S;
	for (int i = 0; i < N; i++)
		cin >> list[i];

	int i = 0, j = 0, sum = 0, minLength = INF;
	while (i < N) {
		sum += list[i];
		if (sum >= S) {
			while (sum - list[j] >= S) {
				sum -= list[j++];
			}
			minLength = min(minLength, i - j + 1);
		}
		i++;
	}
	if (minLength == INF)
		minLength = 0;
	cout << minLength;
	return 0;
}

---