이번 문제는 다이나믹 프로그래밍을 활용하여 해결하였다. 피보나치 수 문제는 워낙 많이 접해봐서 바로 풀 수 있었다. 메모라이제이션을 이용하여 연산의 크기를 줄였다.

점화식은 dp[n]=dp[n-1]+dp[n-2]를 사용하였다.

• n을 입력받는다.
• dp 배열을 [0, 1, 1] 뒤에 0 n개로 채운다.
• 3부터 n까지 반복하는 i에 대한 for문을 돌린다.
  -> dp[i]를 dp[i-1]+dp[i-2]로 갱신한다.
• dp[n]을 출력한다.

Code

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