[BOJ / Python] 1003번: 피보나치 함수

문제: BOJ 1003번

풀이

간단한 dp문제이다. 0 호출횟수와 1 호출횟수 를 저장하는 배열을 만들고, 값이 들어올 때 마다 그 이전값을 이용해 연산해서 저장해주면서 출력한다.

최종코드

import sys

input = sys.stdin.readline

d=[[0]*2]*42
n = int(input())
d[0]=[1,0]
d[1]=[0,1]		#기본값 세팅
for _ in range(n):
    a = int(input())
    if a>1:
        for i in range(2,a+1):		#바로바로 연산
            d[i]=[d[i-1][0]+d[i-2][0],d[i-1][1]+d[i-2][1]]
    print(d[a][0],d[a][1])