백준 #1648 격자판 채우기(동적 계획법)

이번 문제는 플래티넘으로 등급이 매겨진 문제입니다.

 

격자판의 크기가 주어지면, 2x1 미노로 격자판을 채우는 것입니다.  빈 곳이 있으면 안되고, 꽉 채우는 경우의 수를 계산하는 프로그램입니다.

 

일견 어려워보일 수 있겠지만, 동적 계획법을 잘 사용하면 쉽게 풀 수 있습니다.

 

2x1 미노를 세로 또는 가로로 채우는 문제이기 때문에 한줄을 다 채웠을 경우 다음줄에는 말끔하지 않게 되어 있을 수가 있습니다.  예를 들어서 3x6 격자판을 채운다고 해보죠.  첫줄을 채우는 방법은 다음의 두가지입니다.

 

 

두번째 줄의 모양에 따라서 안 채워진 곳은 0, 채워진 곳은 1이라고 한다면, 위의 두 패턴은 001과 100이 됩니다.

초기 패턴은 000이라고 할 수 있습니다.  그러면 우리는 점화식으로 다음과 같이 놓을 수 있습니다.  x 패턴에서 y패턴으로 갈 수 있다는 표현을 $x\to y$라고 한다면, 다음과 같이 점화식을 쓸 수 있습니다.

 

$$d_0(m)=1$$

$$d_y(m-1)=\sum _{x\to y}{d}_x(m)$$

 

이렇게 하면, 3x6 격자판을 채울때 초기 패턴값 $d_{000}(6)=1$이 되겠죠.

$d_{100}(5)=1,d_{001}(5)=1,d_{111}(5)=1$이 될겁니다. 

이런식으로 다음줄도 계산하면, $d_{000}(4)=3,d_{011}(4)=1,d_{110}(4)=1$이 될겁니다. 

다음은 $d_{100}(3)=4,d_{001}(3)=4,d_{111}(5)=3$,

$d_{000}(2)=11,d_{011}(2)=4,d_{110}(2)=4$,

$d_{100}(1)=15,d_{001}(1)=15,d_{111}(5)=11$, 

$d_{000}(0)=41,d_{011}(2)=15,d_{110}(2)=15$

 

이렇게 하면 3x6의 답은 41인 것을 알 수 있습니다.

 

두번째로 갈 수 있는 패턴인가 아닌가를 살펴보는 것은, 패턴을 반전한 다음, 연속된 1이 있는 경우 00을 만들어서 처리를 했습니다.  예를 들어서 현재 패턴이 001이라면 반전하면 110이 됩니다.  11이 연속된 1이므로, 나올 수 있는 패턴은 110, 000이 되는 것이죠.

 

그래서 나온 답들을 살펴보면,

14x14 : 990

13x12 : 1742

10x10 : 5606

 

이 답들을 참조해서 풀어보세요.

저는 파이썬의 딕셔너리를 이용해서 풀었습니다.  총 14x14가 있으니, 미리 답을 구해놓고 풀어도 될 듯 합니다.  좌우대칭이고, 곱한값이 짝수여야하므로, 총 77가지를 미리 계산하시면 $O(1)$로도 계산이 됩니다.  패턴이 2진수로 표현되므로, 전 패턴이 적게 나오는 쪽으로 진행을 했습니다.  즉, n, m 입력받은 것 중 작은 수를 이용해서 패턴에 사용했습니다.