[ Python ] 1003번 피보나치 함수

개요

백준 1003번 피보나치 함수 문제입니다. top-down 형식의 재귀풀이가 아닌 bottom-up 형식의 DP를 사용하여 풀었습니다.

문제

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

1003번: 피보나치 함수

접근법

코드

🤩 : DP

# 메모이제이션

N = int(input())

result = []

for _ in range(N):
    T = int(input())
    dp = [[1, 0], [0, 1], [1, 1], [1, 2]] + [[0, 0] for _ in range(T-3)]
    for i in range(4, T+1):
        dp[i][0] = dp[i - 1][1]
        dp[i][1] = sum(dp[i - 1])
    
    result.append(f'{dp[T][0]} {dp[T][1]}')

for i in result:
    print(i)