파이썬) 백준 알고리즘 | 1003번 : 피보나치 함수

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

1003번: 피보나치 함수

백준 1003 '피보나치 함수' 문제입니다.

피보나치 함수를 동적 프로그래밍으로 구현하고

n-1, n 번째의 피보나치 수를 출력하면 됩니다.

import sys
input = sys.stdin.readline

T = int(input())
dp = [0] * 41
def fibo(x):
    if x == 0:
        return 0
    if x == 1 or x == 2:
        return 1
    if dp[x] != 0:
        return dp[x]
    dp[x] = fibo(x-1) + fibo(x-2)
    return dp[x]

for _ in range(T):
    example = int(input())
    if example == 0:
        print(1,0)
    elif example == 1:
        print(0, 1)
    else:
        print(fibo(example-1), fibo(example))