[백준] 1003. 피보나치 함수 - python3

1003. 피보나치 함수

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

1003번: 피보나치 함수

 

 

내 풀이 - 성공

from sys import stdin
import collections

T = int(stdin.readline())
dp = collections.defaultdict(list)

dp[0] = [1, 0]
dp[1] = [0, 1]

def func(n):
    if n in dp:
        return dp[n]
    else:
        a = func(n-1)
        b = func(n-2)
        dp[n] = [a[0]+b[0], a[1]+b[1]]
        return dp[n]

for t in range(T):
    N = int(stdin.readline())
    dp[N] = func(N)
    print(dp[N][0], dp[N][1])

 

이런 재귀 문제는 시간 초과 나기 쉽상이기 때문에

dp 를 이용해야겠다고 판단했다.

 

딕셔너리 dp 에 [0 출력횟수, 1 출력횟수] 의 형태로 저장해줬다.

우선 고정 값인 0 과 1 에 대한 값은 직접 넣어주고

나머지는 재귀 돌면서 채워갔다.