[백준] 2133번: 타일 채우기 (다이나믹 프로그래밍)

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

2133번: 타일 채우기

 

이 문제는 전형적인 타일링 문제이고 다이나믹 프로그래밍으로 접근해야 한다.

그러나 다른 타일링 문제에 비해 점화식을 생각해내기가 어려웠다.

 

우선 그림을 그려보았다.

 

파이썬 풀이

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