[BOJ 1806] 부분합

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

1806번: 부분합

---

위 문제를 전체 탐색을 하면 O(N^2)으로  N이 100000이어서 시간초과가 난다.

 

투 포인터 알고리즘을 이용하여 풀 수 있다. 배열에 연속된 합의 처음과 끝부분을 가리키는 변수를 만들고 이 변수를 움직여서 합을 구하는 것이다.

 

s = 연속합의 처음 인덱스

e = 연속합의 끝 인덱스 + 1

 

1. 합이 찾는 값 S보다 크거나 같으면, 합을 수열[s]값을 빼고 s에 1을 더한다.

2. e가 수열의 끝이면 더 이상 합이 커질 수 없어 반복문을 끝낸다

3. 합이 작으면 e에 1을 더하고 합에 수열[e]만큼 더하면 된다.

 

즉, s, e 포인터를 움직이면서 연속된 합이 S이상일 때 그 길이를 통해 정답을 구하면 된다.

---

#include <stdio.h>
#include <vector>
#include <algorithm>

#define min(a, b) ((a) < (b)? (a):(b))

using namespace std;

int n, S;
int a[100001];
int ans = 1000000;


int main()
{
	scanf("%d%d", &n, &S);

	for (int i = 0; i < n; i++)
		scanf("%d", a + i);
	int s, e;
	s = e = 0;

	int sum = 0;
	while (s <= e)
	{
		if (sum >= S)
		{
			sum -= a[s];
			s++;
		}
        else if (e == n) break;
		else
		{
			sum += a[e];
			e++;
		}
		if (sum >= S)
			ans = min(ans, e - s);
	}

	if (ans == 1000000)
		ans = 0;

	printf("%d", ans);
}