[백준] 1003. 피보나치 함수 - 파이썬

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

1003번: 피보나치 함수

 

풀이

문제 이름부터 대놓고 피보나치 함수인데..

DP 써야겠죠? Top-Down 방식(재귀)로 구현함.

 

일반적으로 DP의 예시로 많이 나오는 게 피보나치 함수인데,

그거 생각하면서 풀었던 것 같다.

다만 원하는 결과값이 좀 다르므로, 잘 처리해주면 될 듯.

dp = dict()
test = [int(input()) for _ in range(int(input()))]


def fib(n):
    if dp.get(n, -1) != -1:
        return dp[n]
    elif n == 0:
        return [1, 0]
    elif n == 1:
        return [0, 1]
    else:
        dp[n] = [fib(n-1)[0]+fib(n-2)[0], fib(n-1)[1]+fib(n-2)[1]]
        return dp[n]


for i in test:
    print(*fib(i))