1003. 피보나치 함수

동적프로그래밍, 메모이제이션

2주차 알고리즘 수업 과제입니다.

“알고리즘 시간 복잡도 계산하기”

문제 링크

https://boj.kr/1003

입출력 및 제한사항

입력: 정수 $N$ 이 주어진다. (단, $0 \leq N \leq 40$)
출력: $N$번째 피보나치 수를 구하여 출력한다.
시간제한: 0.25초

풀이 :: $O(N)$

Memoization을 사용할 경우, 피보나치 수열은 시간복잡도 $O(N)$에 풀이가 가능합니다.

이 문제는 $n$번째 피보나치 수 $F_n$을 구하기 위해 $F_0$과 $F_1$이 얼마나 호출되었는지를 묻는 문제입니다.

피보나치 함수를 조금만 변형하면 풀이가 가능합니다.

$F_0$과 $F_1$의 호출 횟수를 저장하는 클래스 FibonacciCalledCount를 정의하여 문제를 풀이해보겠습니다.

from __future__ import annotations

from dataclasses import dataclass
from functools import cache
import sys


@dataclass
class FibonacciCalledCount:
    f0: int
    f1: int

    def __add__(self, other: FibonacciCalledCount) -> FibonacciCalledCount:
        return FibonacciCalledCount(self.f0 + other.f0, self.f1 + other.f1)

    def __repr__(self) -> str:
        return f'{self.f0} {self.f1}'


@cache
def fibonacci(n: int) -> FibonacciCalledCount:
    if n == 0:
        return FibonacciCalledCount(1, 0)
    elif n == 1:
        return FibonacciCalledCount(0, 1)
    return fibonacci(n-1) + fibonacci(n-2)


if __name__ == "__main__":
    T = int(sys.stdin.readline())
    for t in range(T):
        N = int(sys.stdin.readline())
        print(fibonacci(N))