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

링크

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

1806번: 부분합

해설

배열 내에서 두 개의 포인터를 가지고 이동하면 되는 문제입니다.

 

연속된 합이 S 이상인 것들 중 가장 길이가 짧은 것이니 오른쪽 포인터를 움직이다가

S이상이 되면 길이 체크 후 다시 왼쪽 포인터를 움직여서 줄이면 됩니다.

 

1. 현재 부분합이 S이상 - 더이상 늘려봤자 의미가 없으므로 다시 줄여야 함

 길이 짧은 것으로 교체

 합에서 TABLE[left] 빼기

 left++

 

2. 현재 부분합이 S 미만 - S이상이 되도록 늘려야 함

 right++

 합에 TABLE[right] 더하기

 

이렇게 두 포인터를 이용해서 부분합이 S이상인 것들 중 최소 길이만 다 확인해주면 됩니다.

 

코드

#include <iostream>
using namespace std;

int N, S, TABLE[100000];

int min(int _a, int _b) {
	if (_a < _b)
		return _a;
	return _b;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> S;

	for (int i = 0; i < N; ++i)
		cin >> TABLE[i];
	
	int left = 0, right = 0, now = TABLE[0], ans = 100001;

	while (right != N) {
		if (now < S) {
			++right;
			now += TABLE[right];
		}
		else {
			ans = min(ans, right - left + 1);
			now -= TABLE[left];
			++left;
		}
	}

	cout << (ans == 100001 ? 0 : ans);

	return 0;
}