백준 문제 중 2133번, DP, ‘타일채우기’

백준 문제 중 2133번

https://www.acmicpc.net/problem/2133

문제

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

입력

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

출력

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

힌트

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

---

풀이

이 문제의 핵심은 각 n만이 가지고 있는 특수한 타일을 생각하는 것이다.

일단 홀수인 경우에는 타일을 완벽하게 채울 수 없으므로 짝수만 따지면된다.

점화식을 구할때까지 직접 그려보며 생각해보자. 처음에 규칙이 없어보이지만 힌트를보고, 3 x 6, 3 x 8 타일을 그려보면 규칙이 보인다.

힌트를 보면 타일의 중간에 3 x 4짜리 타일 두가지

이 중간에 들어 있음을 볼 수 있다. 이 타일을 4의 특수 타일이라 하자. 단, 3 x 0은 1개의 특수타일 3 x 2는 3개의 특수타일을 갖는다.

이 모양의 타일은 3 x 6, 3 x 8 ,… 3 x n 짝수마다 각각의 종류가 존재 함을 알 수있다.

3 x n 중 짝수 n에 대하여 타일을 채우는 모든 방법의 수를 dp[n]에 저장한다고 하자, 그러면 dp[i]를 구하는 방법은

1. dp[i-2]에 3 x 2를 붙이는 방법 즉 dp[2]의 방법수
2. dp[i-4]의 뒤에 4의 특수 타일을 붙이는 방법
3. dp[i-6]의 뒤에 6의 특수 타일을 붙이는 방법
   …
4. dp[0]의 뒤에 dp[i]의 특수 타일을 붙이는 방법
   을 모두 합하여 dp[i]에 저장하면된다. 이때 특수타일의 각 방법의 수는 항상 2가지이다.

이를 수도코드로 표현하면 다음과 같다.

for i in range(4,n+2,2):

        tmp = 0

        for j in range(i-4,-2,-2):

            tmp += dp[j]*2

        dp[i] = dp[i-2]*3 + tmp

이를 파이썬으로 구현하면 아래와같다.

from collections import defaultdict

n = int(input())

dp = defaultdict(int)

 # 3 x 0을 채우는 방법의 수는 1가지, 3 x 2를 채우는 방법은 3가지
 # 초기값 설정
dp[0], dp[2] = 1, 3

 # n이 홀수거나 2이하면 바로 dp[n] 출력
if n%2==1 or n<=2:

    print(dp[n])

else:

     # n이 4이상일때 부터 n까지 진핵
    for i in range(4,n+2,2):

        tmp = 0

         # i-4 부터 0이 될때까지 진행
        for j in range(i-4,-2,-2):

             # 각각의 dp[j]뒤에 특수타일 2가지 경우를 곱함
            tmp += dp[j]*2

         # dp[i-2]뒤에 2개의 타일의 경우 3가지 경우를 곱함
        dp[i] = dp[i-2]*3 + tmp

    print(dp[n])

12
2131