https://www.acmicpc.net/problem/2133
3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.
Code
n = int(input())
dp = [0]*(n+1)
if n > 1:
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])
👨🏻💻 🏃🏻♂️ 🎶