[백준][2749] 피보나치 수 3

suhan0304·2023년 11월 7일

백준 분할 정복 수학 피보나치

백준

목록 보기

28/53

Problem Link : https://www.acmicpc.net/problem/2749

2759번 말고도 2747, 2748, 10826, 10870에 해당하는 피보나치 문제들 또한 이 문서를 참고하자

문제

n이 주어질 때 n번째 피보나치 수를 1,000,000으로 나눈 나머지를 구하여라

입력

첫째 줄, n이 주어진다.

출력

첫째 줄, n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력한다.

풀이에 앞서

기존의 재귀, 단순 반복문으로 피보나치를 계산하던 방법을 이 문제에서 사용하면 실행 시간 초과 오류가 발생할 수 밖에 없다. 그럴 수밖에 없는게 n의 최대값이 $10^{18}$ 이기 때문에 단순 O(N)의 시간 복잡도를 지니고 있는 반복문을 이용한 피보나치 계산도 불가능하다. 당연히 순환 함수(재귀)를 사용해도 실행 시간 초과 문제가 발생한다.

피보나치를 구현하는 방법

1. 무작정 연산 : O(n)

흔히 사용하는 반복문으로 배열을 계속 계산해나가는 방법이나 재귀 함수를 이용한 방법에 해당한다.

2. 행렬을 이용한 연산 : O(log n)

피보나치 수열의 정의를 다시 보면서 행렬식으로 바꾸면 다음과 같다. $F_{i+1}\,=\,F_i\,+\,F_{i-1}\\ F_i\,=\,F_i\,+\,0$
여기서 각 항을 상수와 F로 나눠서 보면 행렬의 곱으로 바꿀 수 있다. $\begin{aligned}\begin{bmatrix}F_{i+1}\\F_{i}\\ \end{bmatrix}\,&=\,\begin{bmatrix}1&1\\1&0\\ \end{bmatrix}\begin{bmatrix}F_{i}\\F_{i-1}\\ \end{bmatrix}\\ &\,=\begin{bmatrix}1&1\\1&0\\ \end{bmatrix}^i\begin{bmatrix}F_{1}\\F_{0}\\ \end{bmatrix}\\ &\,=\begin{bmatrix}1&1\\1&0\\ \end{bmatrix}^i\begin{bmatrix}1\\0\\ \end{bmatrix}\end{aligned}$

이처럼 피보나치수열을 행렬의 식으로 바꾸고 마지막 식처럼 정리할 수 있다. 이제 행렬식의 제곱만 하면 된다. 기존의 수열 연산과 달리 행렬의 n승 연산은 $log_2(N)$ 만에 행렬 곱셈으로 빠르게 구할 수 있다.

3. 일반항을 이용한 연산

연산 과정이 복잡해 생략하고 최종 식이 다음과 같이 나타난다.

F_n\,=\,\frac{1}{\sqrt 5}(\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n

더 자세한 증명 과정은 해당 문서를 참고하자

머리를 싸매던 중 피보나치와 나머지를 혼용한 개념 중 하나인 피사노 주기에 대해 알게되어 문제를 해결 할 수 있었다.

피사노 주기를 알면 굉장히 쉽게 풀 수 있는 문제였다.

피사노 주기?

피보나치 수를 어떤 수 K로 나눌 때, 나머지는 항상 주기를 가지게 되는데 이를 피사노 주기라고 한다.

P를 주기의 길이라고 할 때 N번째 피보나치 수를 M으로 나눈 나머지는 N%P번째 피보나치 수를 M으로 나눈 나머지와 같다.
주기는 M = $10^k$ (k<2)일 때, 항상 15 * $10^{(k-1)}$ 이다.

풀이

n의 범위가 매우 크기 때문에 피보나치의 수를 모두 구하지 말고 피사노 주기를 풀이에 적용시켜 보자. 이 문제에서 M = 1,000,000이다. M = $10^6$ 이므로 구지는 15 * $10^5$ = 1,500,000이다.

따라서 주기의 길이가 1,500,000 이므로 N번째 피보나치 수를 1,000,000으로 나눈 나머지는 N%1,500,000번째 피보나치 수를 1,000,000으로 나눈 나머지와 같다.

실제로 코드만 봐도 굉장히 간단하게 구현 가능하고 실행 시간도 엄청 빨라졌다.

코드

import sys

input = sys.stdin.readline

n = int(input())

M = 10**6
P = 15 * (10**5)

if n == 1:
    print("1")
else:
    arr = [0, 1]
    for j in range(2, n % P + 1):
        arr.append((arr[j - 1] + arr[j - 2]) % M)
    print(arr[n % P])