[백준][DP][Bitmasking] 2133번 타일채우기

문제 

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하시오.

문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/2133)

풀이

저번에 이 문제를 풀려했던적이 있는데 점화식을 세우지 못해서 포기했던 문제였습니다. N이 홀수인 경우에는 0이 된다는 점과 타일의 위치에 따라 규칙을 알 수 없는 특수한 케이스로 점화식을 세우지 못했었습니다. 그러다 bitmasking을 공부하며 관련 문제들을 풀다가 이 문제도 해당분류에 속함을 알 수 있었습니다. dp[i][000~111] 과 같이 표현을 할 수 있고 이는 i-1번째까지 다 채워졌다고 했을 때 i-1번째의 행에 채워진 타일을 bit로 나타냅니다. 다 채워지지 않은 경우를 000, 다 채워진 경우를 111, 두칸만 채워진 경우를 110, 011 한칸만 채워진 경우를 100, 001 로 표현할 수 있습니다.(타일을 채워보면 101, 010과 같은 경우는 생기지 않음을 알 수 있습니다.) 이전 칸에 채워진 값을 이용해서 이후 칸을 채워나가고 최종적으로 구하고자하는 값은 dp[N][111] = dp[N][7] 입니다. 꽤 다양한 경우가 있어서 몇가지만 점화식을 세워보겠습니다. 

dp[i][000](0) = dp[i-1][111](7): i-1번째까지 다 채워져있으며 i번째 행에는 아무런 타일이 채워지지 않은 경우는 i-1번째에서 다채워져있는 경우의 수와 같습니다.

dp[i][100](4) = dp[i-1][011](3): i-1번째까지 다 채워져있으며 i번째 행에는 제일 윗칸의 타일만 채워져있는 경우는 이전 행의 아래 두칸만 채워진채로 윗칸이 비어져있을 때를 의미하며 이 때 윗칸에 1*2 타일을 넣게 되므로 dp[i-1][011] 경우의 수와 같습니다.

dp[i][111](7) = dp[i-1][110](6) + dp[i-1][011](3) + dp[i-1][000](0)

: i-1번째 행까지 차있으면서 i번째 행의 타일이 다 채워진 경우는 i-1번째 행이 다 안채워져있을 때 1*2 타일을 세개 쌓을 수 있는 경우를 만들 수 있습니다. 그리고 i-1번째의 윗칸 2개가 차있을 경우에 아래칸에 1*2를 추가하는 경우 + i-1번째의 아래 2칸이 차있을 경우 윗칸에 1*2 타일을 추가하는 경우도 포함됩니다.

이와 같이 N에 대하여 6가지의 경우를 계산해주어 최종 dp[N][7]을 구하면 원하는 최종결과를 얻을 수 있습니다. 생각보다 꽤 어렵지만 비트를 사용해서 배열에서 사용한다는 점만 떠올리면 점화식을 세울 수 있습니다.

코드

https://github.com/kswim/Algorithm/blob/master/DP/2133.cpp