BOJ - 1806 부분합

주어진 수열 중 연속된 수들의 합이 S 이상이 되는 것 중 가장 짧은 것의 길이를 구하는 문제이다.

문제풀이 전략
수열의 길이가 10만으로 반복문을 중첩하여 사용하면 시간초과가 난다.

따라서 수열을 한번만 탐색하며 길이를 구해야 하므로 투포인터를 활용하였다.

우선 왼쪽을 가리키는 l과 오른쪽을 가리키는 r을 변수로 둔다.

그리고 나서 합이 S보다 작다면 오른쪽을 증가시키며 더해준다.

만약 합이 S보다 작거나 같으면 왼쪽을 빼준 후 증가시킨다.

이 때, 만약 l과 r이 같아지면 길이는 1로 최소가 되므로 바로 종료시켜 준다.
(예시 : S=100, 수열:1,2,3,100 인 경우)

그리고 만약 r이 수열의 끝에 도달하였으나 아직 합이 S보다 작은 경우라면 더의상 S만큼 도달할 수가 남아있지 않았다는 의미이므로 바로 종료시켜 준다.

코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, s;
    cin >> n >> s;

    vector<int> v;
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        v.push_back(x);
    }

    int l = 0;
    int r = 0;
    int sum = v[0];
    int ans = 100001;

    while(1){
        if(sum >= s) {
            ans = min(ans, r-l+1);
            if(l == r){
                break;
            }else {
                sum -= v[l];
                l++;
            }
        }else {
            r++;
            if(r >= v.size())
                break;
            sum += v[r];
        }
    }

    if(ans == 100001)
        ans = 0;
    cout << ans << "\n";
    return 0;
}

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