문제#

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력#

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력#

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

아이디어#

합을 이용한 문제이니 부분합을 이용하고 구간만 필요하니 투 포인터를 이용해서 부분합 배열을 검사해 내가며 길이가 가장 짧은 것을 찾는걸 생각했다.

이 경우 부분합 배열을 모두 탐색해야하므로 $O(N)$의 시간 복잡도를 가져 제한시간과 숫자 범위를 고려할 때 성공할 만하다고 결론지었다.

코드#

#include <cmath>
#include <iostream>
#include <numeric>
using namespace std;

constexpr int INF = numeric_limits<int>::max();

int N, S;

int arr[100001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N >> S;

    for (int i = 1; i <= N; ++i)
    {
        cin >> arr[i];
        arr[i] += arr[i - 1];
    }

    int len = INF;

    int first = 1;
    int second = 1;

    while (second != N + 1)
    {
        int sum = arr[second] - arr[first - 1];
        if (sum >= S)
        {
            len = second - first + 1 < len ? second - first + 1 : len;
            first++;
        }
        else
            second++;
    }

    cout << ((len != INF) ? len : 0);
}

결과

맞았습니다

깃헙링크 : link