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

import sys
input = sys.stdin.readline

def fibo(n):

    if n == 0:
        print(1,0)
        return None
    if n == 1:
        print(0,1)
        return None

    dp = [[0]*2 for _ in range(n+1)]

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

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

t = int(input())

testcase = [0]*t

for i in range(t):
    testcase[i] = int(input())

for i in testcase:
    fibo(i)

이번 문제는 피보나치 수를 구하는 함수에서, fibo(0)과 fibo(1)이 각각 출력되는 횟수를 구하는 문제이다.

 

여태까지 풀었던 피보나치 문제와 동일하게 Bottom-Up 방식을 사용하여 푸는 대신, DP 테이블을 피보나치 수를 저장하는 1차원 리스트가 아니라 0과 1이 호출되는 횟수를 저장하는 2차원 리스트를 활용하였다는 차이점이 있다.

 

다시 한번 DP 알고리즘에 대해 복습해볼 수 있었던 문제였다 :)