[BOJ/python] 1103: 피보나치 함수

문제

✔️ silver 3
다이나믹 프로그래밍

문제 흐름

fibonacci(x)가 출력하는 0, 1의 수는 정해져있다.
각 x마다 output이 정해져있고, fibonacci(x)는 fibonacci(x-1)과 fibonacci(x-2)를 호출하니 두 함수를 호출했을 때의 output의 합과 같다.
연속적으로 같은 방식을 통해 다음 output을 구해나갈 수 있다. => DP

memo[x]에 n = x인 경우 출력하는 0과 1의 수를 튜플의 형태로 저장했다.
fibonacci 함수에서도 그렇듯 초기값은 n이 0인 경우와 1인 경우가 된다.
다음 x에 대해 2부터 n까지 반복하며 memo[x]값을 구한다.
memo[x]값은 다음과 같이 구할 수 있다.
memo[x] = ( memo[x - 1][0] + memo[x - 2][0], memo[x - 1][1] + memo[x - 2][1] )

코드

# 피보나치 함수
# dp

import sys
input = sys.stdin.readline

def fibonacci(n: int):
    if n == 0:
        print("0")
        return 0
    elif n == 1:
        print("1")
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

def dp (n: int):
    if n == 0:
        return 1, 0
    elif n == 1:
        return 0, 1
    memo = [(0, 0) for i in range(n+1)]
    memo[0] = (1, 0)
    memo[1] = (0, 1)

    for x in range(2, n+1):
        val_1 = memo[x - 1][0] + memo[x - 2][0]
        val_2 = memo[x - 1][1] + memo[x - 2][1]
        memo[x] = (val_1, val_2)
    # print(memo)
    return memo[n]


if __name__ == "__main__":
    t = int(input())
    for testcase in range(t):
        n = int(input())
        result = dp(n)
        print(*result)

마무리

아 fibonacci 함수는 문제에 나온 함수를 출력해보기 위해 작성한건데 빼도 상관 없다.
대표적인 dp의 예시인 fibonacci를 이용한 문제인 만큼 간단한 점화식과 눈에 보이는 규칙으로 어렵지 않은 문제였다.