부분합

백준 1806

GOLD IV

1. 문제 내용
2. 해결 방안
3. 풀이 코드

---

문제 내용

문제 링크

해결 방안

길이가 N이고 각각의 성분이 10,000 이하의 자연수인 수열이 있다고 할 때, 연속된 성분의 합이 S 이상인 부분수열 중 길이가 가장 짧은 것을 찾는 문제이다.

매번 두 인덱스 사이의 합을 구하기에는 연산량이 많아지므로, 미리 합을 구해서 사용해야 한다. 자연수 i < j에 수열의 i번째부터 j번째까지의 부분합은 1번째 인덱스부터 j번째 인덱스까지의 부분합에 1번째 인덱스부터 i번째 인덱스까지의 부분합을 뺀 것과 같다. 때문에 각 인덱스별로 1번째 인덱스부터의 부분합을 구해놓으면, 부분합을 구할 때의 시간 복잡도가 O(N)에서 O(1)로 줄어든다. 하지만 이렇게 하더라도 부분합의 범위를 정할 두 인덱스를 이중 for문으로 전부 구하게 되면, 최대 N(N-1)번 반복하기 때문에 시간복잡도가 O(N²)이 나오게 된다. 수열의 길이가 최대 100,000이므로, 전부 조사하는 방법은 너무 오래 걸리기 때문에 두 포인터 알고리즘을 사용해야 한다.

앞서 정리한 내용을 바탕으로 코드를 작성해보면, 우선 수열의 각 성분들을 입력받을 때마다 각각의 인덱스까지의 부분합을 저장한다. 그 다음에는 시작 인덱스와 끝 인덱스에 대한 포인터 두 개를 생성하여 부분합의 범위를 정해준다. 부분합의 범위는 부분합의 크기에 따라 정하게 되는데, 현재 부분합이 최소 부분합인 S보다 작다면, 끝 인덱스를 움직여 부분합의 범위를 더 늘린다. 만약 현재 부분합이 최소 부분합인 S 이상이라면, 시작 인덱스를 움직여 조건에서 벗어날 때까지 부분합의 범위를 줄여본다. 이 과정 중에 부분합의 길이를 기록하며, 최소 범위를 갱신시켜주어야 햔다. 끝 인덱스가 수열의 마지막까지 탐색했거나 시작 인덱스가 끝 인덱스를 넘어설 때까지 반복한다. 끝 인덱스가 수열의 범위를 넘어가면, 시작 인덱스부터 수열의 마지막까지의 합이 S 미만이라는 뜻이므로 탐색을 종료해도 된다. 시작 인덱스가 끝 인덱스를 넘어서는 경우는 수열의 성분 하나만으로 S 이상인 경우만 있으므로, 부분 수열의 합이 S 이상일 때의 부분수열의 최소 길이는 1이기 때문에 탐색을 종료해도 된다.

두 포인터(two pointer)란?

리스트 내에서 각각의 인덱스를 가리키는 두 개의 포인터로 순차적으로 탐색하는 알고리즘이다. 리스트의 특정 위치에서 시작한 두 포인터에 대해, 조건에 따라 각 포인터의 위치를 변경하는 과정을 결과값이 나올 때까지 반복한다. 두 포인터 알고리즘은 탐색하고자 하는 리스트의 길이가 길어질수록 유리한데, 길이가 N인 리스트를 두 개의 인덱스에 대해 전수 조사했을 때의 시간복잡도는 O(N²)이다. 하지만, 투 포인터는 각각의 포인터가 O(N)이기 때문에, 최종적으로는 두 포인터 각각의 시간복잡도를 합한 O(2N)이 나온다.

풀이 코드

#include <iostream>

using namespace std;

// 각 수열의 0번째 인덱스부터 i번째 인덱스까지의 수열의 합 저장
long long permutSum[100001];

int main() {
    // Fast IO
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);

    // 수열의 개수와 최소합 기준 입력
    int n;
    long long s;
    cin >> n >> s;
    
    // 각 수열 입력 및 i번째 인덱스까지의 수열의 합 저장
    long long permut;
    long long sum = 0;
    permutSum[0] = 0;
    for(int i = 1; i <= n; i++) {
        cin >> permut;
        sum += permut;
        permutSum[i] = sum;
    }

    // 두 포인터 생성
    int l = 0;
    int r = 1;
    // 부분 수열의 최소 길이 초기화
    int minLen = n + 1;
    while(l < r && r <= n) {
        // l번째 인덱스부터 r번째 인덱스까지의 부분합 계산
        long long accSum = permutSum[r] - permutSum[l];

        // 부분합이 S 미만이면 부분 수열의 범위 확장
        if(accSum < s)
            r++;
        // 부분합이 S 이상이면 수열의 길이 갱신 및 수열의 범위 축소
        else {
            if(minLen > r - l)
                minLen = r - l;
            l++;
        }
    }
    
    // 길이가 최신화되지 않은 경우, 합을 만드는 것이 불가능한 것으로 간주
    if(minLen == n + 1)
        cout << 0 << endl;
    else
        cout << minLen << endl;
    return 0;
}

---