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

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

1003번: 피보나치 함수

---

 

[풀이]

- 피보나치 함수가 피보나치 수열과 동일한 점화식 F(n)=F(n-1)+F(n-2)이기 때문에, dp 배열에 그대로 적용해주었다.

 

- 0일 때와, 1일 때를 초기값으로 설정하고 2부터 n까지 점화식을 통해 값을 찾아갔다.

 

T=int(input())
for _ in range(T):
    n=int(input())
    dp=[0]*41
    dp[0],dp[1]=(1,0),(0,1)
    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])