부분합 1806

문제

접근 방법

연속된 수들의 합이라는 부분에 주목하면 된다. S만큼 커졌는지 확인하고 커졌으면 앞에서부터 범위를 좁혀와서 최소 길이를 구하면 된다.

코드

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N, S, sum = 0, ret = 100001, bot = 0;
    cin >> N >> S;
    vector<int> v(N);
    for (int i = 0; i < N; ++i)
    {
        cin >> v[i];
        sum += v[i];
        while (sum >= S)
        {
            if (sum - v[bot] >= S)
            {
                sum -= v[bot++];
            }
            else
            {
                int dis = i - bot + 1;
                ret = ret > dis ? dis : ret;
                break;
            }
        }
    }
    cout << (ret == 100001 ? 0 : ret);
}

풀이

누적합 문제를 풀어봤다면 쉽게 접근할 수 있지 않을까 싶다.
입력받으며 범위를 넓혀가고 조건을 충족하면 앞에서 좁혀오면 된다.
틀렸기에 왜 틀렸나 했는데 할 수 없으면 0을 출력해야 하는데 -1을 출력해버렸다.