C++로 합이 n이 되는 연속 수열의 개수 구하기

양의 정수 n이 주어졌을 때, 연속된 양의 정수들로 이루어진 목록 중 그 합이 정확히 n이 되는 경우의 수를 구하는 문제입니다.

예를 들어 n = 15라면 정답은 4가 됩니다. 가능한 목록은 다음과 같습니다.

• [1, 2, 3, 4, 5]
• [4, 5, 6]
• [7, 8]
• [15]

접근 방법: 슬라이딩 윈도우(투 포인터)

이 문제는 슬라이딩 윈도우 기법으로 효율적으로 해결할 수 있습니다. 구간의 시작점(begin)과 끝점(end)을 두 포인터로 관리하면서, 두 포인터 사이 값들의 합(sum)을 조건에 맞게 늘리거나 줄여가며 답을 셉니다.

알고리즘 단계

1. begin := 1, end := 1, x := (n + 1) / 2 로 초기화합니다. 연속된 두 개 이상의 수로 이루어진 수열의 시작값은 n의 절반을 넘을 수 없으므로 탐색 범위를 줄일 수 있습니다.
2. sum := 0 으로 초기화합니다.
3. end <= x 인 동안 다음을 반복합니다.
   • sum에 end 값을 더해 윈도우를 확장합니다.
   • sum >= n 인 동안 다음을 반복합니다.
     • sum이 n과 같으면 count를 1 증가시킵니다. (조건을 만족하는 구간 발견)
     • sum에서 begin 값을 빼고 begin을 1 증가시켜 윈도우를 축소합니다.
   • end를 1 증가시킵니다.
4. count + 1을 반환합니다. 여기서 +1은 숫자 n 하나만으로 이루어진 목록 [n]을 의미합니다.

구현 예시

아래 C++ 코드로 위 알고리즘을 확인할 수 있습니다.

#include <iostream>
using namespace std;

int solve(int n) {
    int begin = 1, end = 1, x = (n + 1) / 2, count = 0;
    long int sum = 0;
    while (end <= x) {
        sum += end;
        while (sum >= n) {
            if (sum == n)
                count++;
            sum -= begin;
            begin++;
        }
        end++;
    }
    return count + 1;
}

int main() {
    cout << solve(15);
}

입력

15

출력

4

복잡도 분석

begin과 end 포인터가 각각 최대 n/2번까지 이동하므로 시간 복잡도는 O(n)이며, 추가적인 배열 없이 몇 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다.