백준 2133 - 타일채우기

DP

이 문제를 보고 다이내믹 프로그래밍으로 해결해야 겠다고 생각한다.
n을 직접 가정해보며 점화식을 세웠다.

세로 길이는 정해져 있으니 가로길이를 다르게 하며 나올 수 있는 값을 보았다.

n = int(input())

dp = [ 0 for i in range(31)]
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

  else:
    dp[i] = 0
  
print(dp[n])