[Python] 백준 알고리즘 #1003 피보나치 함수

문제풀이

 

이 문제는 dp를 이용하면 쉽게 풀린다. 먼저 규칙을 찾아보자.

 

DP	0	1	2	3	4	5
0	1	0	1	1	2	3
1	0	1	1	2	3	5

DP 점화식을 세우면,

dp[n] = [dp[n-1][0]+dp[n-2][0], dp[n-1][1]+dp[n-2][1]] 이다.

 

import sys

input = sys.stdin.readline

T = int(input())

dp = [[1,0],[0,1]]

for i in range(2,41):
    dp.append([dp[i-1][0]+dp[i-2][0],dp[i-1][1]+dp[i-2][1]])

for i in range(T):
    n = int(input())
    print(dp[n][0],dp[n][1])

 

www.acmicpc.net/problem/1003

1003번: 피보나치 함수