[Python] BOJ 2748: 피보나치 수 2

문제

• https://www.acmicpc.net/problem/2748
  

피보나치 수?

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 와 같은 형태의 수열을 '피보나치 수열'이라고 한다.
각 수는 0과 1에서부터 시작된 앞 두 숫자의 합이 된다.

풀이

from sys import stdin
input = stdin.readline
N = int(input())

dp = [0] * (N+1)
dp[1] = 1

for i in range(2, N+1):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[N])

위 그림은 for문의 마지막만을 남겨둔 상태의 디버거 모습이다. 리스트 dp에 피보나치 수열이 저장된 것을 확인할 수 있다. N번째 수(10)은 55가 들어가게 된다.