[python] 백준 - 2133. 타일 채우기

🤔문제 해결

• S2 | DP

이런문제는 역시 단골 DP문제

일단 손으로 구해봤다.

          i == 0, 2, 4, 6 ( 홀수 일 경우는 제외함 )

경우의수 == 1, 3, 11, 41

 

점화식

dp[i] = dp[i-2] * 3 + (dp[2] ~ dp[i-2]) * 2 + 2

i경우의수 = 이전의 경우의 수 * 3 + 이전의 경우의 수 들 * 2 + i만 만드는 경우

 

💻소스 코드

N = int(input())
if N % 2:
    print(0)

else:
    dp = [0] * (N + 1)
    dp[0], dp[2] = 1, 3

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

    print(dp[N])
 

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

2133번: 타일 채우기