[백준 알고리즘] 1806번 부분합

pos에 부분합의 가장 왼쪽 위치,

len에는 부분합의 길이,

sum에는 부분합의 합계를 저장한다.

0~n까지 i for문을 돌면서

len을 1증가하고 list[i]를 sum에 더한다.

이 때, sum이 s이상이라면

sum이 s보다 작을 때까지 while문을 돌면서

부분합의 최소 길이를 구한다.

 

 

 

#include <iostream>

using namespace std;

int list[100000];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	long long s;
	cin >> n >> s;

	for(int i=0; i<n; i++){
		cin >> list[i];
	}

	int pos = 0, len = 0, res = 100001;
	long long sum = 0;
	
	for(int i=0; i<n; i++){
		sum += list[i];
		len ++;
		while(sum >= s){
			res = min(len, res);
			sum -= list[pos];
			pos ++;
			len --;
		}
	}
	if(res == 100001)
		res = 0;
	cout << res;
	return 0;
}