백준 Gold4 - 타일 채우기

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	58551	21635	17169	36.772%

문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

예제 입력 1 복사

예제 출력 1 복사

힌트

아래 그림은 3×12 벽을 타일로 채운 예시이다.

풀이

트리를 이용해서 각각에 오프닝에 대해 가능한 패턴을 반복하다보면 다음 그림과 같이 어떤 규칙성을 발견할 수 있다.

(이미지 유실)

오프닝은 무조건 가로 블럭으로 시작해야 된다. 높이가 3칸이므로 무조건 가로 블럭 한칸이 들어가야 된다. 가로 블럭으로 부터 나올 수 있는 오프닝은 3가지인데 첫번째로 가로블럭이 3개가 와버리면 그 3 x 2 블럭이 완성 되므로 그다음에 올 블럭의 경우의 수는 $DP(K - 2)$ 이 된다. 그다음 두 번째 오프닝을 보면 세로 블럭이 한칸 들어오게 되는데 이떄 2가지 경우의 수가 생긴다.

세로 블럭을 하나 더 두어 완성된 3 x 2 블럭이 생기는 경우
가로 블럭들이 들어와서 완성되지 못하는 패턴이 생기는 경우 처음 경우는 마찬가지고 완성된 3 x 2 블럭 이후 $K- 2$ 의 새로운 블럭으로 생각할 수 있으므로 $DP(K-2)$ 가 된다. 두번쨰 경우 부터 또 마찬가지로 2가지 경우의 수가 반복되는데
세로 블럭을 세워 패턴을 완성시키는 경우
가로 블럭을 두어 패턴을 반복하는 경우 이후 계속 2가지 경우의 수로 분할 되어 반복된다.

마지막 세번째 오프닝은 두번째 오프닝을 상하 반전시킨 것과 같으므로 이후 같은 패턴을 반복하게 된다.

그래서 이를 점화식으로 표현하면 다음과 같다.

\begin{align} DP(K) &= DP(K-2) + 2*\bigl[ DP(K-2) +DP(K-6) + DP(K-8) + \cdots + DP(K-2N) \bigr] \\ &= DP(K-2) + 2*\sum\limits_{N=1}^{K/2}DP(K-2N) \end{align}

이때 $DP(0)$ 은 0칸에서 만들 수 있는 가짓수이므로 아무것도 넣지 않는 방법이 한개뿐 이므로 1이 된다. $DP(1)=0$ 이다 왜냐하면 $DP(K)$ 는 칸을 “완성”시키는 경우의 수를 말한다. 따라서 $DP(0)$ 도 아무것도 안채우고 완성이 가능하므로 $DP(0)=1$ 이 된다. $DP(2)=3$ 이므로 $DP(4)$ 를 구해보면

\begin{align} DP(4) &= DP(2) + 2*(DP(2) + DP(0)) \\ &= 3 + 2*(3 + 1) = 11 \end{align}