[Baekjoon] 1003번 : 피보나치 함수

실버 3

1003번: 피보나치 함수

 

문제 풀이

다이나믹 프로그래밍의 기초

보텀업(bottom-up) 방식으로 0번째부터 차근차근 dp 리스트를 채워나간다.

 

0과 1이 호출되는 횟수도 피보나치 수열과 마찬가지로 점화식을 세울 수 있다.

 i의 0이 호출되는 횟수 = (i-1)의 0이 호출되는 횟수 + (i-2)의 0이 호출되는 횟수
 i의 1이 호출되는 횟수 = (i-1)의 1이 호출되는 횟수 + (i-2)의 1이 호출되는 횟수

 

코드

t = int(input())
for _ in range(t):
    dp = [0] * 41
    dp[0], dp[1] = (1, 0), (0, 1)

    n = int(input())
    if n > 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])