[ 백준 ] 2749 피보나치 수

// 문제 요약

 

$N$이 ${10}^{18}$ 이하의 자연수일 때

$N$번째 피보나치 수를

${10}^{6}$으로 나눈 나머지를 구하여라.

 

// 사고

 

피보나치 수를 구하는 간단한 문제처럼 보이지만

DP로 풀었을 경우 $O(N)$ 의 복잡도를 가지므로

$N$이 $10^{18}$승 정도 되는 큰 수인 경우

DP로 돌리는 루프가 너무 오래 돌아가게되는 문제가 생긴다.

그러므로 $O(N)$을 따르되

$N$에 비례하지 않는 새로운 방법을 찾아야 한다.

 

// 풀이

 

우선 이 문제의 풀이는 정해져 있다.

알면 풀고 모르면 못푸는 수학 문제다.

 

여기서는 피사노 주기를 이용하며

피사노 주기 중에서도 특수한 경우에 해당하는

${10}^{k}$ 로 나누었을 때의 주기를 이용한다.

 

피보나치 수를 어떤 정수 $m$으로 나눈 나머지는

반드시 주기성을 띄며 이때 주기를 피사노 주기라고 한다.

 

피사노주기를 $p$ 라고 하자

그러면 피보나치 수열을 $m$으로 나눈 나머지 값은

$p$ 번마다 동일한 숫자가 등장하므로

나머지 수열의 $N$ 번째 숫자는

$N$을 $p$로 나눈 나머지 번째의 숫자와 같다.

 

그러므로 최초의 $p$번째 숫자까지만 구한 후

그중에서 $N$을 $p$로 나눈 나머지번째의 숫자만 구해주면

빠르게 원하는 값을 얻을 수 있다.

 

특히 피사노 주기는 피보나치 수열을 나누는 $m$의 값이

$m = {10}^{k}$ 이고 $k>2$ 일 때

피사노 주기 $p$의 값은

$p = 15{\times}{10}^{k-1}$라는 특수한 값을 가진다.

 

이 성질을 이용해서 코드를 구현하면 아래와 같다.

 

### 백준 2749 피보나치 수
# https://www.acmicpc.net/problem/2749

import sys
n = int(sys.stdin.readline())

m = 10**6
p = 15*m//10

a_i, a_ii = 0, 1
for _ in range((n)%p-1):
    a_i, a_ii = a_ii, (a_i + a_ii)%m

print(a_ii)

 

여기서는 $1e6$ 과 같은 float 형을 사용하지 않고

**을 사용하여 int 만으로 계산을 이어나가는 것이 좋으며

특히 최종 값에 $m$을 나눠주기 보다

매번의 계산에서 나머지를 구해주는 것이 더 좋다.

 

숫자가 커질수록 계산해야하는 비트수가 늘어나므로

작은 수를 여러면 연산하는 것이 더 이득이 되기 때문이다.