[백준] 2133 - 타일 채우기 Python

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

2133번: 타일 채우기

 

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

 

예시를 보자면 3x12 타일을 채우는 한 가지 경우는 위와 같을 수 있겠다.

 

먼저, 타일을 추가하기 위해 고유한 모양을 확인한다. 타일의 모양이 고유하지 않다면 추가하는 경우의 수가 중복되므로 고유한 경우만 타일을 추가해주어야 한다.- 3X2 타일의 경우 고유한 모양이 3개 존재한다.

 

- 3X4 타일의 경우 고유한 모양이 2개 존재한다.

- 3x6 타일의 경우 고유한 모양이 2개 존재한다.

- 3x8, 3x10.. 의 경우도 마찬가지로 고유한 모양이 2개 존재한다.

고유한 모양의 가로길이를 k 라 했을 때 이를 일반화하면 다음과 같다.

-  3가지 (k = 2)

-  2가지 (k >= 4, k 는 짝수)

-  0가지 (k >= 3, k 는 홀수)

 

고유한 모양의 타일을 이어붙여 가로길이 i 를 만드는 방법의 가지수를 d[i] 라 하면 d[i] 는 다음과 같이 정리할 수 있다.

- 가로의 길이가 i-2 인 경우에 k=2 를 이어붙인 경우 d[i-2]*3 가지

- 가로의 길이가 i- k (k= 4, 6, 8, 10...i) 일 때 d[i-k]*2 가지

i-k 가 0 인 경우 고유한 모양으로 가로길이 i 를 만드는 2가지 경우에 해당한다. d[0] = 1 로 초기화해 이를 계산한다.

 

코드로 작성하면 다음과 같다.

from sys import stdin

dp = [0]*(31)
dp[0] = 1
for i in range(2, 31, 2):
    dp[i] += dp[i-2]*3
    for k in range(4, i+1, 2):
        dp[i] += dp[i-k]*2

N = int(stdin.readline())
print(dp[N])

추가로 위처럼 특정한 형태로 (ex dp[i] += dp[i-k]*2) 반복될때, 항들의 유사한 부분을 파악하면 이중 for 문을 없앨 수 있는 경우가 많다.

d[2] = d[0]*3
d[4] = d[2]*3 + d[0]*2
d[6] = d[4]*3 + d[2]*2 + d[0]*2
d[8] = d[6]*3 + d[4]*2 + d[2]*2 + d[0]*2
...

다음과 같이 유사한 부분이 보일 것이다.

- d[6] = d[4]*3 + d[2]*2 + d[0]*2
- d[8] = d[6]*3 + d[4]*2 + d[2]*2 + d[0]*2

유사한 부분을 대입한다.

- d[8] = d[6]*3 + d[6] - d[4]

이를 일반화한 식은 다음과 같다.

d[i]  = d[i-2]*4 - d[i-4]

 

위 점화식을 이용해 코드로 작성하면 다음과 같다.

from sys import stdin

dp = [0]*(31)
dp[0], dp[2] = 1, 3
for i in range(4, 31, 2):
    dp[i] += dp[i-2]*4 - dp[i-4]
    
N = int(stdin.readline())
print(dp[N])