[백준][투 포인터] 1806 부분합 c++구현

목차

 

 

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

1806번: 부분합

문제

 

 

보기 전에 참고하면 좋을 것 같습니다..

https://be-senior-developer.tistory.com/36

[투 포인터] c++구현 및 백준 2003 예제 설명

 

 

코드 구현

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
vector<int> arr;
int main() {
	int N, S, i, num, ans =1000001, s=0, e=0, sum=0;
	cin >> N >> S;

	for (i = 0; i < N; i++) {
		cin >> num;
		arr.push_back(num);
	}

	while (s < N) {

		if (sum < S) {
			if (e != N ) { // 종착점이 끝에 도달 시 
				sum += arr[e];
				e++;
			}
			else {    // 합이 목표값보다 작은 경우 종착점 증가
				sum -= arr[s];
				s++;
			}
		}
		else {  //합이 목표값보다 크거나 같은 경우 시작점 증가
			sum -= arr[s];  
			s++;
		}
		
		if (sum >= S)   //합이 S이상인 경우
		{
			ans = min(ans, e - s);  //최솟값 갱신
		}
	}
	if (ans == 1000001)  //갱신이 안됬을 경우 0출력
		cout << 0;
	else
     	cout << ans;

}