[백준] 부분합

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

1806번: 부분합

우선 문제부터 간단하게 요약하면, 

 

길이 N의 수열이 주어질 때, 이 수열에서 연속된 수들의 부분합 중 그 합이 S 이상이 되는 것중 가장 짧은 것의 길이를 출력해야 하는 문제입니다. 

 

<Solution>

어렵지 않은 투포인터와 누적합을 이용하는 문제입니다. 실제 구현은 아래와 같습니다. 주의 해야 하는 점은 만약 합을 만들지 못하는 경우 0 을 출력해야 한다는 점만 주의해서 코드를 구성하면 됩니다. 

 

#include <iostream>

using namespace std;

int N, S;
int numArray[100000+10];
int pSumArray[100000+10];

int main(){
    cin >> N >> S;

    // get numArray
    for(int i = 1; i<=N; i++){
        cin >> numArray[i];
    }

    // build prefix sum array
    for(int i = 1; i<=N; i++){
        pSumArray[i] = pSumArray[i-1] + numArray[i];
    }

    // two pointer
    int s = 0, e = 0;
    int minLength = 987654321;

    while(e<=N && s<=N){
        int curSum = pSumArray[e]-pSumArray[s];

        if(curSum<S) e++;
        else{
            minLength = min(minLength, e-s);
            s++;
        }
    }

    if(minLength == 987654321) minLength = 0;
    cout << minLength << endl;

    return 0;

}