[백준 1806] 부분합

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

백준의 부분합 문제입니다.
배열의 구간내에서 특정 구간의 합이 S 이상인 구간 중 가장 짦은 구간을 구하는 문제입니다.
저는 투포인터에 약한 모습을 보이기에 강화하고자 문제를 풀었습니다.

풀이방법입니다.

두개의 포인터를 의미하는 l (left), r (right)를 0번 idx로 정합니다.

그리고 해당 l과 r 2개 사이에서 가지고 있는 포인터의 구간의 합을 구합니다. (초기 값은 0번 idx만이므로 0번 idx의 값입니다.)

그리고 만약 구간합이 S보다 적다면 더 많은 구간을 포함해야 하므로 r를 오른쪽으로 한칸 이동하고 다시 구간합을 구합니다.

만약 구간합이 S보다 크거나 같다면 구간의 길이를 더 줄여볼 여지가 있다는 의미이므로 l을 오른쪽으로 옮기고 구간의 합을 다시 구합니다.

이 때 구간을 바꿀 때 매번 구간내의 합을 구하면 시간복잡도면에서 투포인터를 하는 의미가 없으므로 이전에 구한 합에서 빼거나 더하는 식으로 진행합니다.

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int N,S,mn=1e9;
vector<int> v;
int main(){
    cin >> N >> S;
    for(int i=0;i<N;i++) {
        int input; cin >> input;
        v.push_back(input);
    } 
    int l = 0, r= 0;
    long long sum = v[0];
    while(l<=r && r<N){
        if(sum<S) {
            if(++r < N) sum += v[r];
        }
        else {
            sum -= v[l];
            mn = min(mn,r-l+1);
            l++;
        }
    }
    if(mn == 1e9) cout << 0;
    else cout << mn;
}