[BOJ] 백준 2133번 타일 채우기 - 파이썬(Python)

문제

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

입력

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

출력

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

 

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

2133번: 타일 채우기

 

💡 풀이 및 코드

n = int(input())
dp = [0] * (n + 1)
dp[0] = 1

for i in range(2, n+1, 2):
    dp[i] += dp[i-2] * 3
    for j in range(0, i-2, 2):
        dp[i] += dp[j] * 2

print(dp[n])

간단해 보이지만 만만하게 봐서는 안되는 DP 문제이다. 점화식을 세워보면 다음과 같다. 우선, n이 홀수일 때는 타일을 채울 수 없으므로 0을 출력해야하고, n이 짝수라는 가정 하에 점화식을 적어보면 다음과 같다.

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

이때, dp[0]에는 임의로 1이 저장되어 있어햐 한다. 위와 같은 점화식이 나오는 이유는 3*2 타일을 채우는 경우의 수는 3개, 나머지 3*n 타일을 채운 경우의 수는 각각 2개 이기 때문이다.