백준 2133 - 타일 채우기 (Python)

https://acmicpc.net/problem/2133 

2133번: 타일 채우기

점화식이 잘 안 떠올라서 성가셨다.

n = int(input())
dp = [0 for _ in range(31)]
dp[2] = 3
for i in range(4,n+1,2) : # 어차피 홀수는 만들 수가 없다.
    if i%2 == 0 : # 핵심은 2*3 이상의 블록, 즉 4*3, 6*3 등의 블록은 두 개만 만들 수 있다는 것.
        dp[i] = dp[i-2] * 3 + sum(dp[:i-2]) * 2 + 2
print(dp[n])