[BOJ] 부분합 1806번 C++

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

접근 방식

 

먼저 누적합을 모두 구해준다

en, st이 N보다 작은 경우 반복문을 돌면서

현재 구간의 누적합이 S보다 큰지 확인한다

만약 S 보다 크면 구간의 길이를 갱신하고

st++해준다

이때 en값을 갱신하지 않는 경우는 st - en 의 구간이 S보다 큰 첫 구간이기 때문이다!

그리고 마지막 최소 구간의 길이가 없다면 0을 출력하고 그렇지 않다면 최소 구간의 길이를 출력한다

 

코드

 

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll pSum[100003];
int N, ans = 0x7f7f7f7f;
ll S;

int main() {
    cin>>N>>S;
    for(int i=1; i<=N; i++) {
        int x; cin>>x;
        pSum[i] = pSum[i-1] + x;
    }

    int st = 1, en = 1;

    while(en <= N && st <= N) {
        ll sum = pSum[en] - pSum[st-1];
        if(sum >= S) {
            ans = min(ans, en-st+1);
            st++;
        } 
        else en++;
    }
    if(ans == 0x7f7f7f7f) cout<<0;
    else cout<<ans;
}