[Gold 4] 1806 부분합

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

 

투포인터를 사용하는 문제이다.

초기 문제를 분석할 때 투포인터를 사용해야한다는 것을 알 수 있었다.

 

10 15
5 1 3 5 10 7 4 9 2 8

 

위 숫자가 주어질 때 15를 만들기 위해서는 5와 10을 사용하면 최소의 개수로 15라는 값을 만들 수 있다.

 

이는 투포인터를 사용해 0번째 인덱스부터 N-1 번째 인덱스까지 부분합을 구하면 알 수 있다.

즉, 초기 0번째 인덱스의 값이 5이므로 15보다 작게된다. 그러면 1을 더한다.

그후, 3 5, 10까지 더햇다면 24가 되므로 목표 값인 15를 초과하게 된다.

그러면 24에서 5를 뺸 값을 확인한다. 확인 결과 목표 값을 초과하므로 1, 3을 순차적으로 뺸다.

최종적으로 5 + 10을 통해 15를 구할 수 있다.

 

위 과정을 투 포인터를 사용해 이후에 나올 수 있는 더 짧은 경우도 구할 수 있다.

 

#include <iostream>
using namespace std;

int N, S;
int arr[100001];
int answer = 987654321;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>N>>S;
    for(int i = 0;i<N;i++)
        cin>>arr[i];
    
    
    int s = 0, e = 0;
    int sum = 0;
    while(e<=N){
        if(sum >= S){
            answer = min(answer,(e - s));
            sum -= arr[s++];
        }
        else{
            sum += arr[e++];
        }
    }
    if(answer == 987654321)
        answer = 0;
    
    cout<<answer;
}