[백준 BOJ / Python] 2749번 피보나치 수 3 (Pisano Period)

문제

n이 주어졌을 때, n번째 피보나치 수를 구하는 문제이다.

이 문제의 조건은 다음과 같다.

피보나치 수는 0과 1로 시작한다.

0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다.

그다음 2번째부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

예를 들어, n=17일 때까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

풀이

• 피보나치 수는 특정 숫자로 나누었을 때 나머지가 항상 주기를 갖는다는 특징이 있다. 이를 피사노 주기(Pisano Period)라고 한다.
  예를 들어 피보나치 수를 4로 나누었을 때 나머지 주기는 6이다.

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13
Fn (피보나치 수)	0	1	1	2	3	5	8	13	21	34	55	89	144	233
Fn % 4	0	1	1	2	3	1	0	1	1	2	3	1	0	1

 

• $M = 10^k$일 때, $k > 2$ 라면, 주기는 항상 $15 × 10^(k-1)$이다. 
• 즉, 100번째에 있는 피보나치 수를 4로 나눈 나머지를 구할 때 피사노 주기를 이용한다면, 3번 만에 답을 구할 수 있다.

알고리즘

1. 1000000으로 나눈 나머지의 피사드 주기를 구한다. (p = 1500000)
2. 입력받은 n을 p로 나눈 나머지를 다시 n으로 정의한다.
3. 피보나치 수의 특징에 따라 n번째 피보나치 수를 구한다.
   이때, 1000000으로 나누는 것을 잊지 말자.

Python 코드

k = 1000000
n = int(input())
# 피사드 주기
p = 15*k//10
n %= p
# 피보나치 수 Fi = Fi-2 + Fi-1
f1,f2 = 0,1
for i in range(n-1):
    f1,f2 = f2,(f1+f2)%k
print(f2)

문제출처

2749번: 피보나치 수 3