바닥공사 [dp]

# 가로길이 n, 세로길이 2인 바닥
# 1*2, 2*1, 2*2 타일로 덮개를 채우는 모든 경우의 수
# n-1일 때의 타일을 n번째의 타일에서 이용 -> DP

n=int(input())
dp=[0]*(1001)

dp[0]=1 # 2*1 타일 채우는 경우의 수
dp[1]=3 # 2*2 타일 채우는 경우의 수
# dp[2]=dp[0]+dp[1]+1

for i in range(2,n):
    dp[i]=(dp[i-1]+2*dp[i-2])%796796


print(dp[n-1])

• 점화식을 세우는 법 숙지
• 일반화를 통해 n과 n-1, n-2의 관계식을 찾기