이 문제에서는 크기가 2n인 배열 arr[]이 주어집니다. 우리의 목표는 동적 프로그래밍(Dynamic Programming)을 활용하여 모든 부분 집합에 대한 합계(Sum over Subsets)를 구하는 프로그램을 작성하는 것입니다.
문제 정의
다음 함수를 계산해야 합니다.
F(x) = Σ Ai (단, x & i == i)
즉, i가 x의 비트마스크(bitmask) 부분 집합일 때 해당하는 모든 Ai의 합을 구하는 것입니다.
예제로 이해하기
입력: A[] = {5, 7, 1, 9}, n = 2
출력: 5 12 6 22
설명: n = 2일 때 x의 값은 총 4가지(0, 1, 2, 3)입니다. 각각의 함수 값을 계산하면 다음과 같습니다.
F(0) = A0 = 5
F(1) = A0 + A1 = 5 + 7 = 12
F(2) = A0 + A2 = 5 + 1 = 6
F(3) = A0 + A1 + A2 + A3 = 5 + 7 + 1 + 9 = 22
동적 프로그래밍 접근 방법
이 문제를 동적 프로그래밍으로 해결하려면 각 마스크(mask)를 살펴보며 그 마스크의 비트 단위 부분 집합을 찾아야 합니다. DP 테이블에 부분 집합 정보를 저장하면 중복 계산을 크게 줄일 수 있습니다. 특정 인덱스의 비트가 설정(set)되어 있든 해제(unset)되어 있든, 해당 인덱스는 최대 2n개의 마스크에 의해 여러 번 방문될 수 있기 때문입니다.
i번째 비트를 기준으로 다음과 같은 점화식을 세울 수 있습니다.
- i번째 비트가 설정된 경우:
DP(mask, i) = DP(mask, i-1) + DP(mask ⊕ 2i, i-1) - i번째 비트가 해제된 경우:
DP(mask, i) = DP(mask, i-1)
C++ 구현 예제
#include <iostream>
using namespace std;
const int N = 1000;
void SumOverSubsets(int a[], int n) {
int sum[1 << n] = {0};
int DP[N][N];
for (int i = 0; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
if (j == 0)
DP[i][j] = a[i] + a[i ^ (1 << j)];
else
DP[i][j] = DP[i][j - 1] + DP[i ^ (1 << j)][j - 1];
} else {
if (j == 0)
DP[i][j] = a[i];
else
DP[i][j] = DP[i][j - 1];
}
}
sum[i] = DP[i][n - 1];
}
for (int i = 0; i < (1 << n); i++)
cout<<sum[i]<<"\t";
}
int main() {
int A[] = {5, 7, 1, 9};
int n = 2;
cout<<"The sum over subsets is \t";
SumOverSubsets(A, n);
return 0;
}실행 결과
The sum over subsets is 5 12 6 22
정리
SOS DP(Sum over Subsets Dynamic Programming)는 비트마스크 DP 기법 중 하나로, 모든 마스크에 대해 자신의 부분 집합들의 합을 O(n · 2n) 시간 복잡도로 효율적으로 계산할 수 있습니다. 단순한 브루트포스 방식(O(4n))과 비교하면 상당한 성능 향상을 얻을 수 있어, 비트마스크를 활용하는 다양한 조합론·최적화 문제에서 널리 사용됩니다.