이 튜토리얼에서는 곱이 K보다 작은 부분 수열(subsequence)의 개수를 구하는 프로그램을 C++로 작성해 보겠습니다.
문제 정의
음이 아닌 정수로 구성된 배열과 하나의 값 k가 주어집니다. 우리의 목표는 배열에서 만들 수 있는 모든 부분 수열 중, 각 원소들의 곱이 k보다 작은 부분 수열의 개수를 세는 것입니다.
예를 들어 배열이 [1, 2, 3, 4]이고 k = 10이라면, 곱이 10 미만인 부분 수열은 총 11개가 존재합니다.
접근 방법: 동적 계획법(DP)
모든 부분 수열을 일일이 생성하면 지수 시간이 걸리므로, 동적 계획법을 활용하여 효율적으로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
- dp[i][j] = 배열의 앞 j개 원소만 고려했을 때, 곱이 i 이하가 되는 부분 수열의 개수
- j번째 원소를 포함하지 않는 경우: dp[i][j-1]
- j번째 원소(arr[j-1])를 포함하는 경우: arr[j-1] ≤ i이고 0보다 클 때, dp[i / arr[j-1]][j-1] + 1을 더합니다. 여기서 +1은 해당 원소 하나만으로 이루어진 새로운 부분 수열을 의미합니다.
구현 예제
#include <bits/stdc++.h>
using namespace std;
// 곱이 k보다 작은 부분 수열의 개수를 세는 함수
int count_sub(vector<int> &arr, int k){
int n = arr.size();
int dp[k + 1][n + 1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= k; i++) {
for (int j = 1; j <= n; j++) {
// 현재 원소를 포함하지 않는 경우
dp[i][j] = dp[i][j - 1];
// 현재 원소를 포함할 수 있는 경우
if (arr[j - 1] <= i && arr[j - 1] > 0)
dp[i][j] += dp[i / arr[j - 1]][j - 1] + 1;
}
}
return dp[k][n];
}
int main(){
vector<int> A;
A.push_back(1);
A.push_back(2);
A.push_back(3);
A.push_back(4);
int k = 10;
cout << count_sub(A, k) << endl;
}실행 결과
11
코드 설명
배열 [1, 2, 3, 4]와 k = 10이 주어졌을 때, 곱이 10 미만인 부분 수열은 다음과 같습니다.
- 길이 1: {1}, {2}, {3}, {4} → 4개
- 길이 2: {1,2}, {1,3}, {1,4}, {2,3} → 4개 ({3,4}는 곱이 12이므로 제외)
- 길이 3: {1,2,3} → 1개
합계는 총 11개이며, 프로그램의 실행 결과와 일치합니다.
시간 및 공간 복잡도
- 시간 복잡도: O(k × n) — 두 개의 중첩 반복문으로 DP 테이블을 채웁니다.
- 공간 복잡도: O(k × n) — 2차원 DP 테이블을 저장해야 합니다.
단순한 완전 탐색(O(2ⁿ))에 비해 훨씬 효율적이며, 특히 k와 n이 크지 않은 경우 실용적인 성능을 보여줍니다.