[백준] 1806: 부분합 (C++)

Baekjoon 1806

문제

제목처럼 부분합을 구하는 문제이다.

1,2,3,4 배열이 있을 때, 1 2 3 4 1 2 1 3 1 4 2 3 2 4 3 4 1 2 3 1 2 4 2 3 4 1 2 3 4와 같이 모든 조합이 가능 한 원소의 합이다.

이 집합의 원소들의 합이 S 이상이 되는 것 중 원소가 연속되어 있고 짧은 것을 찾는 것이다.

입력

1. 첫 번째 줄에 수열의 길이 N과 부분합 S가 주어진다. (10 ≤ N < 100,000, 0 < S ≤ 100,000,000)
2. 두 번째 줄에 길이 N인 수열이 주어집니다. 수열의 각 원소는 10,000 이하의 자연수이다.

출력

합이 S 이상이 되는 가장 짧은 부분 수열의 길이를 출력합니다. 만약 그러한 부분 수열이 없다면 0을 출력한다.

아이디어

이 문제를 해결하기 위해 슬라이딩 윈도우(Sliding Window) 기법을 사용한다. 시간 복잡도는 O(N)이다.

슬라이딩 윈도우:

1. 두 개의 포인터 start와 end를 사용합니다. 처음에는 둘 다 수열의 시작을 가리킨다.
2. end를 오른쪽으로 이동시키며 현재 부분합을 갱신한다.
3. 부분합이 S 이상이 되면, start를 오른쪽으로 이동시키며 부분합을 최소화한다.
4. 이 과정을 반복하여 조건을 만족하는 가장 짧은 부분 수열의 길이를 찾는다.

CODE

#include <iostream>
#include <vector>
using namespace std;

void init() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);
}

int main() {
    init();
    int N, S;
    cin >> N >> S;
    vector<int> arr(N);
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    int minLength = N + 1;
    int sum = 0;
    int start = 0;

    for (int end = 0; end < N; end++) {
        sum += arr[end];

        // 부분합이 S 이상이 되는 경우, start를 증가시켜가며 최소 길이를 찾는다.
        while (sum >= S) {
            minLength = min(minLength, end - start + 1);
            sum -= arr[start++];
        }
    }

    if (minLength == N + 1) {
        cout << 0;
    } else {
        cout << minLength;
    }

    return 0;
}

부연 설명

1. end가 0일 때:

    end: 0, arr[end]: 5, sum: 5

2. end가 1일 때:

    end: 1, arr[end]: 1, sum: 6

3. end가 2일 때:

    end: 2, arr[end]: 3, sum: 9

4. end가 3일 때:

    end: 3, arr[end]: 5, sum: 14

5. end가 4일 때:

    end: 4, arr[end]: 10, sum: 24

   이때, sum이 S 이상이므로 start를 증가시켜 부분합을 줄인다. 그러니까 15이상이면 15미만이 될 때 까지 줄이면 start가 슬라이딩처럼 앞으로 당겨져 가는 것이다.

    start: 1, sum after removing arr[start-1]: 19, minLength: 5
    start: 2, sum after removing arr[start-1]: 18, minLength: 4
    start: 3, sum after removing arr[start-1]: 15, minLength: 3
    start: 4, sum after removing arr[start-1]: 10, minLength: 2

6. end가 5일 때:

    end: 5, arr[end]: 7, sum: 17

   다시 sum이 S 이상이므로 start를 증가시켜 부분합을 줄인다.

    start: 5, sum after removing arr[start-1]: 7, minLength: 2