BOJ 1806번: 부분합

문제

문제 바로가기> BOJ 1806번: 부분합

1806번: 부분합

 

풀이

연속된 부분 수열의 합이 S 이상 되는 것 중 가장 짧은 것의 길이를 구하는 것이므로, 두 포인터를 이용해서 O(N) 안에 구할 수 있다!

 

#include<iostream>
#define MAX 100001
using namespace std;

int N, S;
int num[MAX];

void input(){
    cin >> N >> S;
    for(int i=0; i<N; i++) cin >> num[i];
}

void solution(){
    int ans = MAX;
    int l=0, r=0, sum=num[0];

    while(1){
        if(S <= sum){ // 합이 S 이상
            ans = min(ans, r-l+1); // 가장 작은 수열의 길이 update
            sum -= num[l++]; // 하나 줄여봄 (<-줄여도 되려나?)
            if(N-1 < l) break; 
        }
        else{ // 합이 S 미만
            r++; // 하나 늘려봄 (S 이상이 되기 위해)
            if(N-1 < r) break;
            sum += num[r];
        }
    }
    if(ans == MAX) cout << 0;
    else cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solution();
}