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

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

1806번: 부분합

 

이중 for문으로 구현하면 시간 초과가 날 것이다. 투 포인터를 사용하면 O(N)의 시간복잡도로 해결할 수 있다. 투 포인터에 대한 설명은 '알고리즘' 파트에서 확인할 수 있다. 투 포인터를 이 문제로 설명하니 이해하는 데 도움이 많이 될 것이다. 링크 바로가기!

 

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


int main() {
	int N, S;
	cin >> N >> S;
	
	int* ary = new int[N];
	
	for (int i = 0; i < N; i++)
		cin >> ary[i];
	
	int start = -1, end = -1, sum = 0;
	int Min = 100000;

	while(end < N) {
		if (sum < S) {
			end++;
			sum += ary[end];
			continue;
		}
		if (sum >= S) {
			Min = min(Min, end - start);
			start++;
			sum -= ary[start];
			continue;
		}
	}

	if (Min == 100000)
		cout << 0 << endl;
	else
		cout << Min << endl;

	delete[] ary;

	return 0;
}