문제 링크

문제 해설이 아닌 풀이하면서 거쳐간 생각들을 기록하는 글입니다.


문제

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

입력

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

출력

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



접근 과정

0.5초라는 짧은 시간제한을 맞추기 위해 누적합을 만들고 투 포인터 알고리즘을 적용하였다. 투 포인터를 의도한건 아니었는데 구현하고보니 그렇게 되었다.
미리 수열의 첫번째 수부터 현재 위치까지의 부분합을 누적한 누적합 배열을 만들고, 수열에서 (A, B] 구간의 부분합은 누적합 B에서 누적합 A를 뺌으로써 구할 수 있다.
만약 부분합이 S보다 작다면 수열이 길어질 필요가 있으므로 B를 1 증가시키고, S보다 크거나 같다면 수열이 짧아질 필요가 있으니 A를 1 증가시켜 전체 배열을 탐색하다보면 구하고자하는 최소 길이를 확인할 수 있다.
구현의 편의를 위해 배열의 0번 인덱스에는 0을 채워넣었다.


소스 코드

#include <iostream>

int main() {
    std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);

    int n, s;
    int prefixSum[100001];
    prefixSum[0] = 0;

    std::cin >> n >> s;
    for (int i = 1; i <= n; ++i) {
        int num;
        std::cin >> num;
        prefixSum[i] = prefixSum[i - 1] + num;
    }

    int begin = 0;
    int end = 0;
    int minLength = 100001;
    while (end <= n) {
        int total = prefixSum[end] - prefixSum[begin];

        if (total >= s) {
            if (minLength > end - begin) {
                minLength = end - begin;
            }
            ++begin;
        } else {
            ++end;
        }
    }

    std::cout << (minLength == 100001 ? 0 : minLength);
    return 0;
}