[개쉬운 풀이] 백준 1806 부분합 CPP (12일차)

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

 

문제

 

생각

1. 연속된 부분합이라는 단어를 보고 투포인터를 고려하였다. 

2. 부분합 중에서 합이 S 이상이 되는 것 중, 가장 짧은 길이를 구하여야 한다.

3. 그렇다면 누적합보다 크거나 같으면 왼쪽에서 빼고, 작으면 오른쪽을 더하면 된다.

 

풀이

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

int N;
long long S;
vector<int> v;

void input(){
    cin >> N >> S;
    for(int i = 0; i < N; i++){
        int x;
        cin >> x;
        v.push_back(x);
    }
}

void sol(){
    if(v[0] == S){
        cout << 1 << endl;
        return ;
    }

    int left, right;
    left = 0;
    right = 1;

    long long sum = v[0] + v[1];
    int answer = N+1;
    
    while(left <= right && right < N){
        if(sum >= S){
            answer = min(answer, right-left+1);
            sum -= v[left];
            left++;
        }
        else {
            right++;
            sum += v[right];
        }
    }
    if(answer == N+1) cout << 0 << endl;
    else cout << answer << endl;
}

int main(){
    input();
    sol();

    return 0;
}