SOS DP

어떤 원소 N개짜리 집합에서 모든 부분집합에 대해 어떤 연산을 한 결과를 전부 더한 값을 알고 싶을 때가 있다. 간단하게 비트마스킹으로 구현하면 이렇게 된다.

 

for (int mask = 0; mask < (1<<N); mask++)
    for(int i = 0; i < (1<<N); i++)
        if ((mask & i) == i)
            F[mask] += A[i];

 

mask는 N개 비트로 이루어져 있는 정수이고, i번째 비트가 켜졌다는 말은 i번 원소가 포함되어 있는 부분집합이라는 말이다. 이때 mask & i를 확인해 주면 mask의 부분집합이 되는 집합들만 확인할 수 있고, 이에 A 연산을 취한 값을 F 배열에 더해 저장해 준다. 시간복잡도는 \(\mathcal O((2^N)^2) = \mathcal O(4^N)\)이다.

 

for (int mask = 0; mask < (1<<N); mask++) {
    F[mask] = A[0];
    for(int i = mask; i > 0; i = (i-1) & mask) {
    	F[mask] += A[i];
    }
}

 

이렇게 짜면 더 효율적이다. mask부터 시작하면서 1씩 빼고 mask의 부분집합이 되도록 and 연산을 한번 취해주면 mask에서 꺼진 비트들은 i에서도 꺼져있기 때문에 더 빠르게 탐색을 할 수 있다. 시간복잡도는 \(\displaystyle \sum_{k=0}^N \binom{N}{K} 2^K = (1+2)^N = 3^N\)이므로 아래 코드는 \(\mathcal O(3^N)\)으로 풀 수 있다. 하지만 더 효율적으로 풀 방법이 있다.

 

 

---

 

만약 어떤 상태가 101000라고 하자. 그럼 위 코드에서 i=101000인 상태는 총 16번 나오게 된다. 111111부터 101000까지 4개의 0인 비트중 하나라도 켜진 상황은 i에서 1씩 빼는 과정에서 필연적으로 지나게 될 과정이다.

그럼 집합을 정의하자

\[S(\text{mask}) = \{x|x\subseteq \text{mask}\}\]

\[S(\text{mask}, i) = \{x|x\subseteq\text{mask and mask}\oplus x<2^{i+1}\}\]

어떤 집합 mask에 대해서 \(S(\text{mask})\)는 mask의 부분집합들, \(S(\text{mask}, i)\)는 mask의 부분집합들 중에서 i번째 비트 이전으로는 모두 같은 집합이다. mask가 101000인 경우 111000은 S에 속하지 않는다. 그럼 \(S(\text{mask}, i)\)를 다음과 같이 확장할 수 있다.

\[S(\text{mask}, i) = \begin{cases}S(\text{mask}, i - 1) & i\text{번째 비트가 없는 경우}\\ S(\text{mask}, i - 1) \cup S(\text{mask}\oplus 2^i, i - 1) & i\text{번째 비트가 있는 경우}\end{cases}\]

이 과정을 통해 S 테이블을 채우게 되면 N개의 비트에 대해서 순차적으로 계산해보면 되므로 \(\mathcal O(N2^N)\)으로 계산을 완료할 수 있다. 코드는 아래와 같다.

 

for (int i = 0; i < (1<<N); i++) F[i] = A[i];
for (int i = 0; i < N; i++) for (int mask = 0; mask < (1<<N); mask++) {
	if(mask & (1<<i)) F[mask] += F[mask ^ (1<<i)];
}

 

코드를 보면 \(F[i]\)를 전처리하고(솔직히 이건 아래 for문에 합칠 수 있을거 같다) 모든 mask에 대해 i번째 비트가 있을 때만 F를 업데이트 해준다. 왜냐면 그렇지 않은 경우는 그냥 \(F[\text{mask}]\)의 값을 그대로 가져올 것이기 때문에 더할 필요가 있을 때만 더해서 업데이트 해주면 된다.