[코드트리 챌린지] 가장 짧은 부분합

[실력진단 테스트]

[문제]

https://www.codetree.ai/missions/8/problems/shortest-subtotal?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

[문제 풀이]

투 포인터를 이용한 기본적인 문제이다.

start 포인트와 end 포인트를 두고 start가 n이 되기 전까지 혹은 end가 해당 범위를 벗어나기 전까지 돌리면서 가장 짧아지는 거리를 파악하자.

[회고]

.

[코드]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n,s;
    cin>>n>>s;
    vector<int> arr(n);
    for(int i = 0;i<n;i++){
        cin>>arr[i];
    }
    int start = 0;
    int end = 1;
    int total = arr[0];
    int answer = 2000000000;

    while(start < n && end <= n){
        if(total < s){
            total += arr[end];
            end++;
        }
        else if(total >= s){
            total -= arr[start];
            start++;
            answer = min(answer, end - start);
        }
    }

    (answer == 2000000000) ? cout<<-1 : cout<<answer + 1<<endl;

    return 0;
}