BOJ #11444 피보나치 수 6

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

BOJ #11444 피보나치 수 6

문제 풀이

주어진 입력이 너무나도 크다. $O(n)$으로 구해도 답이 없는 수준이다. 따라서 기존 DP 기반으로 피보나치 수를 구하면 여지없이 시간초과가 날 것이다. 따라서 제곱의 형태로 곱해나가 정답을 도출하는 $O(log\ n)$해법을 생각해내야 한다.

이 문제는 초기값을 $\begin{pmatrix}f_2&f_1\f_1&f_0\end{pmatrix}$으로 설정해두고 그에 대한 제곱값이 피보나치 수의 형태로 만들어진다는 사실을 모르면 해결하기가 쉽지 않다. $\begin{pmatrix}f_2&f_1\f_1&f_0\end{pmatrix}= \begin{pmatrix}1&1\1&0\end{pmatrix}$이고 $\begin{pmatrix}1&1\1&0\end{pmatrix}^2=\begin{pmatrix}2&1\1&1\end{pmatrix}=\begin{pmatrix}f_3&f_2\f_2&f_1\end{pmatrix}$임을 알 수 있어 이 점을 이용해야 한다.

python 코드

import sys
input = sys.stdin.readline

def mutiply(arr1, arr2):
    R, C, M = len(arr), len(arr2[0]), len(arr1[0])
    sol = [[0 for _ in range(C)] for _ in range(R)]
    for i in range(R):
        for j in range(C):
            b = 0
            for k in range(M):
                b += arr1[i][k] * arr2[k][j]
            sol[i][j] = b % 1000000007
    return sol

def solve(n):
    if n == 1:
        return matrix
    t = solve(n // 2)
    t = multiply(t, t)
    if n % 2 == 1:
        t = multiply(t, matrix)
    return t
N = int(input())
matrix = [[1, 1], [1, 0]]
if N > 1: # N이 1보다 크면
    result = solve(N - 1) # [0][0]은 f_2부터 시작이므로 N - 1을 입력
    print(result[0][0])
else: # N이 1이면
    print(matrix[0][0])