[dp/백준] 2133번: 타일 채우기

-문제: https://www.acmicpc.net/problem/2133

n이 홀수인 경우에는 dp의 값이 0이다.(홀수이면 1x1 공간이 남는데 이를 채울 방법은 없기 때문이다)

그래서 짝수로 진행했다.

n=2,4,6일때의 값을 구했는데, 점화식을 구하는게 어려웠던 문제다. 인접한 두항으로 점화식을 만드는게 아니라 짝수로 인접한 세 항을 가지고 만드는 문제였다.

예시에서 n=4일때 새롭게 만들 수 있는 타일 구조가 있으므로 이부분에 유의해야한다 

f(2)=3

f(4)=11

f(6)=41

 

-정답풀이:

이전에 푼 것과 for j 문이 다른데, 내가 생각한 대로 해도 정답이 떴다 

n = int(input())
dp = [0] * 31
dp[0] = 1
for i in range(2, n + 1, 2):
    dp[i] += 3 * dp[i-2]
    for j in range(0, i - 3, 2): #0부터 n-4까지의 값은 2를 곱해서 더해준다
        dp[i] += 2 * dp[j]
        
print(dp[n])