연속된 부분 수열의 합

문제 링크

연속된 부분 수열의 합

아이디어

1. 가장 단순하게 생각하여 모든 부분 수열을 구하는 방법은 \(O(N^2)\) 의 시간 복잡도를 요구한다.
   • 배열의 크기가 \(10^6\) 이므로, 이는 시간 제한에 걸린다.
2. 비내림차 수열이 주어진다면, \(\sum_{k=i}^{j} S_k < \sum_{k=i}^{j+1} S_k\) 를 만족한다. (\(S_k \ge 1\))
   • 또한, \(\sum_{k=i+1}^{j} S_k < \sum_{k=i}^{j} S_k\) 도 만족한다.
3. 부분 수열은 연속된 인덱스로 구성된다.
   • 즉, \([i, j]\) 에 대해서 \(\sum_{i}^{j} S\) 를 구하는 것
   • 문제에서 요구하는 것은 \(\sum_{i}^{j} S = k\) 가 되는 \([i, j]\)의 집합의 원소
4. 2, 3번에서 기인하여 아래와 같은 결론을 도출
   • \(\sum_{l=i}^{j} S_l < k\) 라면, \(j\) 을 증가시켜서 부분 수열의 합을 크게 만든다.
   • \(\sum_{l=i}^{j} S_l > k\) 라면, \(i\) 를 증가시켜서 부분 수열의 합을 적게 만든다.

4번에서 기술한 것처럼 구현한다면, 현재까지의 누적합 정보를 유지하면서 새로운 원소들에 대해서만 탐색을 진행한다.

또한, 탐색 범위는 항상 후보해를 포함하므로 항상 최적해를 구할 수 있음이 보장된다. (엄밀한 증명은 노트로..)

알고리즘의 시간 복잡도는 \(i, j\) 가 최대 증가할 수 있는 범위가 sequence의 크기이므로 \(O(N)\) 의 시간에 문제를 해결할 수 있다.

소스코드

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

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer = {-1, 0x3f3f3f3f};
    // [i, j)
    int i = 0, j = 0, ac_sum = 0;
    const int size = sequence.size();
    while (j <= size) {
        if (i < j && ac_sum >= k) {
            if (ac_sum == k && answer[1] - answer[0] > j - i) {
                answer[0] = i, answer[1] = j;
            }
            ac_sum -= sequence[i++];
        } else {
            ac_sum += sequence[j++];
        }
    }
    answer[1]--;
    
    return answer;
}