백준 1806 부분합 (C++)

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

#include <iostream>
#include <vector>

#define INF 987654321

using namespace std;

vector<int> arr;
vector<int> prefix;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, S;
    int ans = INF;
    cin >> n >> S;

    arr.resize(n);
    prefix.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        if (!i) {
            prefix[i] = arr[i];
        } else {
            prefix[i] = prefix[i - 1] + arr[i];
        }
    }

    int s = 0;
    int e = 0;

    do {

        int sum = s != 0 ? prefix[e] - prefix[s - 1] : prefix[e];

        if (sum >= S) {
            ans = min(ans, e - s + 1);
            s++;
        } else {
            e++;
        }

    } while (s <= n - 1 && e <= n - 1);

    if (ans == INF) {
        cout << 0;
    } else {
        cout << ans;
    }


    return 0;
}

1. 문제

n의 길이의 수열과 숫자 s가 주어진다. 수열의 부분합이 s 이상이 되는 부분수열 중 가장 짧은 것의 길이를 구하라. 단, 해당하는 부분수열이 존재하지 않을 경우 0을 출력한다.

2. 풀이

최대 길이 10만의 수열에 시간 제한이 0.5초이므로 누적합을 사용하여 구한다.

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        if (!i) {
            prefix[i] = arr[i];
        } else {
            prefix[i] = prefix[i - 1] + arr[i];
        }
    }

우선 수열을 입력받으면서 누적합을 계산하여 저장해준다.

    int s = 0;
    int e = 0;

    do {

        int sum = s != 0 ? prefix[e] - prefix[s - 1] : prefix[e];

        if (sum >= S) {
            ans = min(ans, e - s + 1);
            s++;
        } else {
            e++;
        }

    } while (s <= n - 1 && e <= n - 1);

인덱스 s부터 e까지의 합을 구하고, 이를 비교할 것이다. 해당 부분수열의 합을 구하고, 부분합이 S 이상인 수열을 찾았다면, 해당 수열의 길이를 갱신해주고, 최소 길이를 구하는 것이 목표이므로 s를 오른쪽으로 옮겨 수열의 길이를 줄인다.

 만약 부분수열의 합이 S 이하일 경우 수열의 합을 늘려야 하므로 e를 옮겨준다.

 if (ans == INF) {
        cout << 0;
    } else {
        cout << ans;
    }

만약 해당하는 부분수열을 찾았다면 ans를, 찾지 못했다면 0을 출력하면 정답을 구할 수 있다.