[백준 | Python] #11444 - 피보나치 수 (cache decorator)

11444번: 피보나치 수 6

문제

$n$번 째 피보나치 수를 $10^9+7$로 나눈 나머지를 구하여라. $n$은 $10^{18}$보다 작거나 같은 자연수이다.

아이디어

$n$이 매우 크다. 단순하게 기본적인 피보나치 재귀 함수를 구현해서는 불가능하다.

따라서 다음과 같이 생각해 보았다.

1. 일반항을 통해 구하기 -> 일반항에 $\sqrt 5$가 포함되어 계산이 간단하지 않다. 점화식에 포함된 제곱을 분할정복을 사용한다 하더라도 많은 제곱을 할 수록 부동소수점의 오차가 쌓일 것이다. -> 불가능

2. 점화식을 통한 분할정복을 통해 구하기 -> $f(2n)=g(f(n), f(n+1))$와 유사한 형태의 점화식이 존재할 것이다. (아마?) 이를 이용해 상대적으로 짧은 시간에 문제를 해결할 수 있을 것이다.

구현

점화식을 구하기 귀찮았다. 대충 이 문제를 구글링 하니 바로 찾을 수 있었다.

 

$f(2n) = f(n)\times(2f(n-1) + f(n))$

$f(2n+1) = f(n+1)^2 + f(n)^2$

참고: BOJ - 11444 피보나치 수 6 해결 전략 (C++) (velog.io)

 

이를 통해 재귀함수만 구현하면 된다.

다만 아무 생각 없이 재귀만 구현하면 재귀 시에 무수히 많은 가지가 펼쳐지며 엄청난 개수의 $f(1)$ 내지 $f(2)$를 계산하게 될 것이다.

 

따라서 피보나치 수를 어느 정도 저장하며 재귀를 구현해야 한다.

이때 피보나치 수를 저장하는 딕셔너리나 리스트를 만들어둘 수도 있겠지만 나는 파이썬에서 기본적으로 제공하는 cache decorator를 사용하였다.

 

decorator란, def 구문 위에 @어쩌고가 달린 것을 말한다.

대충 함수에 자동적으로 특별한 기능을 추가해 준다고 생각하면 된다.

 

@cache는 functools 모듈을 불러와 사용할 수 있으며 이를 사용하면 해당 함수는 동일한 인자값에 대한 리턴값을 캐시에 저장하게 된다.

다시 말해, 딕셔너리나 리스트를 만들 필요 없이 알아서 함수의 리턴값을 기억해 계산량을 줄여준다는 것이다.

 

결과적으로 decorator를 통해 import 구문을 포함하여 단 두 줄만으로 귀찮은 메모리 구현 없이 문제를 해결할 수 있다.

코드

from functools import cache

MOD = 1_000_000_007

@cache
def fib(n):
    if n <= 2:
        return 1
    elif n % 2 == 0:
        return (fib(n//2) * (2*fib(n//2-1) + fib(n//2))) % MOD
    else:
        return (fib(n//2+1)**2 + fib(n//2)**2) % MOD

print(fib(int(input())))

후기

데코레이터에 대해 알게 되고 백준에서도 한번쯤 사용해 보고 싶었는데 드디어 제대로 사용해 보았다.