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

문제 출처: https://www.acmicpc.net/problem/1806

1806번: 부분합

투 포인터를 활용하여 구간합을 구하는 문제이다.

6 10

9 8 6 5 7 10이 있다고 할때 처음 start, end 포인터는 0 idx에 있다.

1. 부분합이 S 미만이라면 end++ 을 한다.

2. 부분합이 S 이상이라면 start++을 한다.

 

9 8 6 5 7 10 현재 부분 합 : 9

9 8 6 5 7 10 현재 부분 합 : 17 --> 부분합이 S를 넘었으므로 최소 길이를 2로 갱신한다. 

9 8 6 5 7 10 현재 부분 합 : 8

9 8 6 5 7 10 현재 부분 합 : 14

9 8 6 5 7 10 현재 부분 합 : 6

9 8 6 5 7 10 현재 부분 합 : 11

9 8 6 5 7 10 현재 부분 합 : 5

9 8 6 5 7 10 현재 부분 합 : 12

9 8 6 5 7 10 현재 부분 합 : 7

9 8 6 5 7 10 현재 부분 합 : 17

9 8 6 5 7 10 현재 부분 합 : 10 --> 최소길이 1으로 갱신

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include <string>

using namespace std;


int arr[100001];


int main(void)

{
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int N, S; cin >> N >> S;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}



	int start = 0, end = 0;
	int min = 1234567;

	int nowVal = 0;
	nowVal += arr[end];
	while (start != N) {
		
		if (nowVal >= S) {
			if (min > end - start+1)min = end - start + 1;
			
			nowVal -= arr[start];
			start++;
			
			
		}
		else {
			
			if (end != N - 1) {
				end++;
				nowVal += arr[end];
			}
			else {
				break;
			}
		}

		

	}

	if (min == 1234567)cout << "0";
	else cout << min;

}