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

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

 

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

 

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

 

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

 

 

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

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

 

\[ d_0(m) = 1 \]

\[ d_y(m-1) = \sum_{x \rightarrow 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 입력받은 것 중 작은 수를 이용해서 패턴에 사용했습니다.