[백준] 2133 타일 채우기 파이썬

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

2133번: 타일 채우기

점화식 작성에 앞서 그림으로 문제를 이해하는게 편할것 같아서 그림을 그려보았다.

우선 n이 홀 수 일 때는 개수가 맞지않아 경우의 수는 모두 0이므로 짝 수일 때만 생각하면 된다.

n = 2 일 때 세가지 경우가 생긴다

n = 4 일 때는 그림과 같이 양쪽에 세로 타일 하나씩 사용하고 나머지는 가로 타일만 사용한 모양 두가지와, n=2 일 때 모양을 두번 조합한 경우가 생긴다. 이 때 가능한 총 경우의 수는 2 + 3 * 3 = 11 이다.

 

경우의 수 조합을 위해 두 부분으로 나누어 계산을 했는데 왼쪽은 dp(n)인 경우를 나타내고, 오른쪽은 세로 타일 두개만 사용한 모양을 나타낸다

 

n = 6 일 때도 양쪽에 세로 타일과 나머지는 가로 타일을 사용한 모양과, 첫 두칸은 n=2일 때 모양 + n=4일 때 모양, n=일 때 모양 + n=4일 때 모양을 조합한 경우로, 2 + dp(2) * 2 + dp(4) * 3 = 41 이다.

 

위와 같은 규칙에 따라 dp(8)은 2 + dp(2) * 2 + dp(4) * 2 + dp(6) * 3 = 153 이다

이렇게 점화식을 구해 작성한 코드는 아래와 같다.

n = int(input())
dp = [0] * 31
dp[2] = 3
dp[4] = 11

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

print(dp[n])