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

1x2와 2x1의 타일로 3xN의 타일을 채우는 방법의 수를 구하는 문제

첫번째로, N이 홀수라면 채울 수 없다

• 타일의 면적은 2이다. 그러므로 면적이 2의 배수여야만 채울 수 있지만 n이 홀수일 경우 2의 배수가 아니기때문에 채우기 불가능.

두번째로, 점화식을 구한다.

• 2일 경우는 3가지의 경우의 수가 있다. 그리고 4일 경우는 독자적인 경우 2가지를 포함한 11이다.
• dp[i-2]와 옆 2자리는 3가지이므로 dp[i-2] * 3
• 이후 dp[i-4]와 옆 4자리는 독자적인 경우 2가지 이므로 dp[i-4]*2를 더해준다. 같은 맥락으로 모든 dp[:i-2]에 대해 2를 곱한값을 더한다.
• 점화식은 dp[i] = dp[i-2] x 3 + dp[ :i-4] x 2 + 2

n = int(input())
if n==1:
    print(0)
else:
    dp = [0 for i in range(n + 1)]
    dp[2] = 3
    for i in range(4, n+1):
        if i % 2 == 0:
            dp[i] = dp[i-2] * 3 + sum(dp[:i-2]) * 2 + 2

    print(dp[n])