[BOJ/python] 10826번 피보나치 수 4

https://www.acmicpc.net/problem/10826

10826번: 피보나치 수 4

문제 해석
피보나치 수열의 n번째 항의 값을 출력한다.

---

코드

import sys
from collections import deque

input = sys.stdin.readline
fibolist = deque([0, 1, 1])
n = int(input())

if n != 0:
    for i in range(3, n+1):
        fibolist.append(fibolist[-1] + fibolist[-2])
        fibolist.popleft()
    print(fibolist[-1])
else:
    print(0)

---

문제 풀이
아주아주 간단한 다이나믹 프로그래밍 문제다.

리스트를 만들어 0번째, 1번째, 2번째 항의 값을 미리 저장한다.
이후 3번째 항부터 n번째 항까지의 점화식을 반복해 리스트에 저장하고, 0번째 인덱스의 요소를 제거한다.
그 후 리스트의 -1번째 인덱스의 값이 n번째 피보나치 수열의 값이므로 이를 출력하면 된다.

(이처럼 다이나믹 프로그래밍에서 계산한 값을 저장해 놓는 것을 메모이제이션이라 하며, 계산속도를 증가시킬 수 있다.)
(덱을 적절히 쓰면 메모이제이션으로 인한 메모리 증가를 획기적으로 줄일 수 있다.)
('피보나치 수' 시리즈이며, 브론즈와 실버급 '피보나치 수' 까지는 이 코드를 그대로 복붙해 제출해도 맞는다.)