백준 11444번: 피보나치 수 6 (Python)

접근

피보나치 수열을 행렬의 곱셈 및 분할 정복을 통해 어떻게 풀까 생각을 해봐도 나오지 않아 그 방법을 찾아보았다. 결과적으로는 혼자 생각해서는 쉽게 그 결과를 도출해내지 못했을 것 같다.. n번째 피보나치 수를 다음과 같은 식을 통해서도 구할 수 있다.

$$ \begin{pmatrix}
F_{n + 1} & F_{n}\\
F_{n} & F_{n - 1}
\end{pmatrix} = \begin{pmatrix}
1 & 1\\
1 & 0
\end{pmatrix}^{n} $$

이전 10830번 행렬 제곱에서 사용했던 함수를 그대로 사용하여 문제를 해결할 수 있다.

코드

import sys

c = 1000000007


def multiply(matrix1, matrix2):  # 행렬의 곱셈 함수
    ans = []
    for i in range(len(matrix1)):
        ans.append([])
        for j in range(len(matrix2[0])):
            temp = 0
            for k in range(len(matrix1[0])):
                temp += matrix1[i][k] * matrix2[k][j]
            ans[i].append(temp % c)
    return ans


def power(matrix, p):  # 행렬의 거듭제곱 함수
    if p == 1:
        return matrix
    else:
        temp = power(matrix, p // 2)
        if p % 2 == 0:
            return multiply(temp, temp)
        else:
            return multiply(multiply(temp, temp), matrix)


n = int(sys.stdin.readline())
m = [[1, 1], [1, 0]]
print(power(m, n)[0][1])

더 생각해 볼 것?

피보나치 수를 구하는 방법에는 너무나 여러 종류가 있었다. 잘 정리된 글을 찾아 기록해두려고 한다.

피보나치 수열 알고리즘을 해결하는 5가지 방법

피보나치 수열 알고리즘을 해결하는 5가지 방법

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!