[BOJ] 1806 부분합

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

1806번: 부분합

알고리즘: 투포인터

 

시간복잡도: O(N)

---

접근:

1. 연속된 수들의 부분합

 

-> 연속된 수의 합을 묻는 문제이다.

    BOJ 1644 소수의 연속합 문제처럼 투포인터로 접근하면 된다. (시작점:st, 끝점:en)

 

 

부분합이 S를 넘기면 st++, 길이 갱신(길이의 최솟값 구하기)

부분합이 S보다 작으면 en++

 

#include<iostream>
#include<vector>
#define MIN(a, b) (((a)>(b))?(b):(a))
using namespace std;

int N, S, st, en, minLen=0x7fffffff;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N >> S;
	
	vector<int> D(N+1, 0);
	
	for (int i = 1; i <= N; i++)
	{
		cin >> D[i];
		D[i] += D[i-1];
		
		if (!en && D[i] >= S)
			en = i;
	}
	
	if (!en) //Impossible
	{
		cout << "0";
		return 0;
	}
	
	while (st <= N && en <= N)
	{
		if (D[en]-D[st] >= S)
		{
			minLen = MIN(minLen, en-st);
			st++;
		}
		else
			en++;
	}
	cout << minLen;
	return 0;
}