곱이 K 이하인 모든 부분 수열 개수 구하기 – C++ 재귀 접근법

이 튜토리얼에서는 곱이 K 이하인 부분 수열(sub-sequence)의 개수를 구하는 프로그램을 다뤄보겠습니다.

배열과 값 K가 주어졌을 때, 원소들의 곱이 K 이하가 되는 모든 부분 수열의 개수를 찾는 것이 목표입니다.

핵심 아이디어: 로그 변환

곱셈 값을 직접 다루면 오버플로우 위험이 있고 비교도 번거롭습니다. 이 코드는 로그의 성질을 활용합니다. log(a × b) = log(a) + log(b)이므로, 각 원소의 log2 값을 미리 구해 두면 '곱이 K 이하'라는 조건을 'log2 값의 합이 log2(K) 이하'라는 조건으로 바꿀 수 있습니다.

또한 접두사 합(prefix sum) 배열을 미리 계산해 두면 현재 인덱스 이후의 남은 원소 합을 O(1)에 구할 수 있어, 불필요한 탐색을 줄이는 가지치기(pruning)가 가능해집니다.

예제 코드

#include <bits/stdc++.h>
#define ll long long
using namespace std;
// 기준을 초과해 버려진 부분 수열의 개수
ll discard_count = 0;
ll power(ll a, ll n){
    if (n == 0)
        return 1;
    ll p = power(a, n / 2);
    p = p * p;
    if (n & 1)
        p = p * a;
    return p;
}
// 버려지는 부분 수열을 세는
// 재귀 함수
void solve(int i, int n, float sum, float k,
float* a, float* prefix){
    if (sum > k) {
        discard_count += power(2, n - i);
        return;
    }
    if (i == n)
        return;
    float rem = prefix[n - 1] - prefix[i];
    if (sum + a[i] + rem > k)
        solve(i + 1, n, sum + a[i], k, a, prefix);
    if (sum + rem > k)
        solve(i + 1, n, sum, k, a, prefix);
}
int countSubsequences(const int* arr,
int n, ll K){
    float sum = 0.0;
    float k = log2(K);
    float prefix[n], a[n];
    for (int i = 0; i < n; i++) {
        a[i] = log2(arr[i]);
        sum += a[i];
    }
    prefix[0] = a[0];
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] + a[i];
    }
    ll total = power(2, n) - 1;
    if (sum <= k) {
        return total;
    }
    solve(0, n, 0.0, k, a, prefix);
    return total - discard_count;
}
int main() {
    int arr[] = { 4, 8, 7, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    ll k = 50;
    cout << countSubsequences(arr, n, k);
    return 0;
}

출력 결과

9

동작 원리 살펴보기

원소가 n개일 때 부분 수열의 총 개수는 공집합을 제외하고 2ⁿ − 1개입니다. 따라서 이 알고리즘은 조건을 만족하는 부분 수열을 하나씩 세는 대신, 곱이 K를 초과해서 버려지는(discard) 부분 수열의 개수를 센 뒤 전체 개수에서 빼는 방식을 사용합니다.

• 빠른 거듭제곱(power): 분할 정복 기법으로 2ⁿ을 O(log n) 시간에 계산합니다.
• solve 함수: 인덱스 i까지의 log2 합(sum)이 이미 k를 넘었다면, 남은 원소들을 포함하거나 제외하는 모든 경우(2ⁿ⁻ⁱ개)가 전부 조건을 초과하므로 한 번에 버려집니다.
• 가지치기: 접두사 합으로 남은 원소의 총합(rem)을 구해, 현재 선택을 더해도 k를 넘길 수 없는 경우에는 해당 탐색을 생략합니다.
• 조기 종료: 배열 전체의 곱이 이미 K 이하라면 공집합을 제외한 모든 부분 수열이 조건을 만족하므로 2ⁿ − 1을 그대로 반환합니다.

예제에서 배열 {4, 8, 7, 2}와 K = 50이 주어지면, 곱이 50 이하인 부분 수열은 총 9개임을 확인할 수 있습니다.