[Python]백준 1003번 - 피보나치 함수

1. 문제정보

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

1003번: 피보나치 함수

 

 

2.해결전략

피보나치는 전형적인 다이나믹 프로그래밍 문제입니다. 문제에 친절하게 점화식이 나왔기 때문에 구현만 하면됩니다.

 

 

3. 코드

t = int(input())

dp = [[0 for j in range(2)] for i in range(41)]

dp[0] = [1, 0]
dp[1] = [0, 1]
for _ in range(t):
    n = int(input())
    for i in range(2, n+1):
        dp[i] = [dp[i-1][0] + dp[i-2][0], dp[i-1][1] + dp[i-2][1]]
    
    print(dp[n][0], dp[n][1])