Bit DP

Bit DP란?

이 글에서는 흔히 BitDP 혹은 BitmaskDP라고 부르는 테크닉을 다루도록 하겠습니다.

BitDP를 설명할 때, 가장 자주 다루는 문제인 타일 채우기 문제를 보도록 하겠습니다. (링크)
이 문제는 2*1짜리 타일과 1*2짜리 타일을 이용해 3*n크기의 공간을 모두 채우는 경우의 수를 구하는 문제입니다.
3*n문제를 보기 전에, 2*n문제(링크)를 먼저 봅시다.

2*n짜리 직사각형을 만드는 방법은 아래 두 가지가 있습니다.

2*(n-2) 상황에서 가로 타일 2개 넣기
2*(n-1) 상황에서 세로 타일 1개 넣기

dp[i] = 2*i를 채우는 경우의 수 라고 정의한다면, 점화식은 dp[i] = dp[i-1] + dp[i-2]가 됩니다.

문제 풀이

3*n문제는 어떨까요? 각 열에는 3개의 칸이 있습니다. 각각의 칸은

채워져 있거나
안 채워져 있거나

두 가지 상태 중 하나인 것이 분명합니다.
채워져있다면 1 / 그렇지 않다면 0으로, 즉 이진법으로 표현한다면 각 열은 8가지 상태 중 하나입니다.
그러므로 dp[i][j] = i-1번째 행까지는 모두 채우고, i번째 행의 상태가 j가 되는 경우의 수 라고 정의를 하고 문제를 해결합시다.
각 행의 상태는 아래 사진에 있는 8가지만 가능합니다.

한 가지 유의해야 할 점은, i번째 행의 상태가 j가 되는 경우의 수를 구할 때, i-1번째 행까지는 반드시 모두 채워져 있어야 합니다.

i번째 행의 상태가 0이라면, 반드시 i-1번째 행의 상태는 7이여야 합니다.

i번째 행의 상태가 1이라면, i-1번째 행의 상태는 6입니다. 이렇게 되면 맨 아래에 가로 타일을 하나 추가해주면서 i-1번째 행의 상태를 7로 만들 수 있습니다.

i번째 행의 상태가 2, 4인 경우에도 비슷하게 처리가 됩니다.

i가 3이라면 두 가지 상태가 가능합니다. i-1의 상태가 4라면, 아래쪽에 가로 타일 2개를 추가해주면서 i-1번째 행의 상태를 7로 만들 수 있습니다. i-1의 상태가 7이라면, 아래쪽에 세로 타일을 하나 추가해주면 됩니다.

i가 6인 경우에도 비슷하게 처리가 됩니다.

i가 5인 경우에는 아래 그림과 같이 한 가지 경우만 가능합니다.

i가 7인 경우에는 아래 그림과 같이 세 가지 상태가 가능합니다.

모든 경우에 대해 살펴보았으니, 반복문을 이용해 점화식을 계산하면 됩니다.

int dp[n+1][8];
dp[0][7] = 1;

for(int i=1; i<=n; i++){
  dp[i][0] = dp[i-1][7];
  dp[i][1] = dp[i-1][6];
  dp[i][2] = dp[i-1][5];
  dp[i][3] = dp[i-1][4] + dp[i-1][7];
  dp[i][4] = dp[i-1][3];
  dp[i][5] = dp[i-1][2];
  dp[i][6] = dp[i-1][1] + dp[i-1][7];
  dp[i][7] = dp[i-1][0] + dp[i-1][3] + dp[i-1][6];
}

3*n 타일 채우기 문제를 통해 아주 간단하게 BitDP가 뭔지 알아보았습니다.
n 제한이 11~20정도 되는, 생각보다 작지만 O(n!)으로 풀리지 않는 문제 중에 Bit DP가 많이 나온다고 합니다. 그런 경우 대개 시간 복잡도는 O(2ⁿ * n²) 정도가 나옵니다.

그 예시로는 (이 문제)가 있습니다. (풀이 링크)

BitDP에 대해 조금 더 심화된 설명은 (이 블로그)에 있습니다.

Bit DP란?

문제 풀이

추천 문제