[다이나믹 프로그래밍] 바닥 공사 (Python)

이것이 취업을 위한 코딩 테스트다 with 파이썬

---

입력조건

1. 첫째 줄에 N이 주어진다.

 

출력조건

1. 첫째 줄에 2*N 크기의 바닥을 채우는 방법의 수를 796.796으로 나누 나머지를 출력한다.

 

입력예시

3

 

출력예시

5

---

예전에 비슷한 문제를 푼 적이 있었는데, 이번에 스스로 점화식을 세우질 못했다. 최근에 문제풀이를 살짝 소흘히 해서 그런듯 하다...

 

Python code

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

print(dp[n])