백준 1806번: 부분합

문제

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

풀이

시간 복잡도 관련 문제다. 앞서 푼 "수들의 합2"와 굉장히 유사하다. 두 포인터와 cnt를 이용하여 합이 s이상인 가장 짧은 부분합의 길이를 구해주었다.

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n, s, tmp; cin>>n>>s;
    vector<int> v;
    for(int i=0; i<n; i++){
        cin>>tmp;
        v.push_back(tmp);
    }
    int low=0, high=0, sum=0, ans=n+1, cnt=0;
    while(1){
        if(s<=sum){
            if(cnt<ans) ans=cnt;
            sum-=v[low++]; cnt--;
        }
        else if(n<=high) break;
        else {
            sum+=v[high++];
            cnt++;
        }
    }
    if(ans==n+1) cout << 0;
    else cout << ans;
}