[BOJ]1003 피보나치 함수 - python

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

dp를 이용한 기초적인 문제입니다.

피보나치 함수 f(0), f(1) 의 호출횟수가 서로 영향을 주지 않는다는 규칙을 이용하면 쉽게 풀수있습니다.

각각의 함수 호출횟수를 따로 관리하여 저장하면 됩니다.

import sys
 
dp0 = list()
dp0.append(1)
dp0.append(0)
 
dp1 = list()
dp1.append(0)
dp1.append(1)
 
for i in range(40):
    dp0.append(dp0[i] + dp0[i+1])
    dp1.append(dp1[i] + dp1[i + 1])
 
T = int(sys.stdin.readline().rstrip())
 
for _ in range(T):
    n = int(sys.stdin.readline().rstrip())
    print(dp0[n],dp1[n])