[Python] 백준 2133번 : 타일 채우기

문제

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

입력

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

출력

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

예제 입력 1

2

예제 출력 1

3

힌트

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

 

소스코드

n = int(input())

dp = [0] * (n+1)
if n > 1:
    dp[2] = 3
if n > 3:
    dp[4] += dp[2] * 3 + 2

for i in range(6, n+1, 2):
    dp[i] = dp[i-2] * 4 - dp[i-4]

print(dp[n])

dp[n] = dp[n-2] * 3 + dp[n-4] * 2 + dp[n-6] * 2 + ...... + dp[2] * 2 + 2

dp[n-2] = dp[n-4] * 2 + dp[n-6] * 2 + dp[n-8] * 2 + ...... + dp[2] * 2 + 2

 

dp[n] - dp[n-2] = dp[n-2] * 3 - dp[n-4]

dp[n] = dp[n-2] * 4 - dp[n-4]

 

위 점화식을 구현하면 정답이 된다. n이 홀수인 경우는 가능한 경우가 존재하지 않으므로 0을 출력하면 된다.

런타임 에러(Index Error)가 나서 오답을 여러 번 냈던 문제인데, n이 1이하인 경우와 n이 3이하인 경우 각각에 대하여 예외 처리를 해주지 않아서 에러가 발생했었다.