백준 11444: 피보나치 수 6 (파이썬)

문제: https://www.acmicpc.net/problem/11444

11444번: 피보나치 수 6

---

코드

# https://teching.tistory.com/
import sys

def matrixMultiple(matrix1, matrix2):
    res = [[0]*len(matrix2[0]) for _ in range(len(matrix1))]
    for i in range(len(matrix1)):
        for j in range(len(matrix2[0])):
            for k in range(len(matrix1[0])):
                res[i][j] += matrix1[i][k] * matrix2[k][j]
                res[i][j] %= 1000
    return res


def matrixSquare(matrix, b):
    if b == 1:
        return matrix
    divMatrix = matrixSquare(matrix, b//2)
    squareMatrix = matrixMultiple(divMatrix, divMatrix)
    if b%2 == 0:
        return squareMatrix
    else:
        return matrixMultiple(squareMatrix, matrix)

n, b = map(int, sys.stdin.readline().split())
matrix = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
answer = matrixSquare(matrix, b)
for i in answer:
    for j in i:
        print(j%1000, end=" ")
    print("")

해설

너무나도 유명한 피보나치수열 구현하기 문제이다.

그중에서도 분할 정복을 이용해서 구현하는 문제!!

해당 방법으로 문제를 풀기 위해서는 행렬에 대해 알아야 한다. 따라서 이전 문제들을 풀고 오는 것이 좋다.

특히 https://www.acmicpc.net/problem/10830 해당 문제는 꼭 풀어보고 와야 한다. 

10830번: 행렬 제곱

이 행렬 제곱을 피보나치수열에 적용시키기 위해서 피보나치를 행렬식으로 정리할 필요가 있었다.

먼저 피보나치수열의 점화식(0번째부터 시작)을 구해보면

$ f(n+1)= f(n) + f(n-1) $

$ f(n)  = f(n-1) + f(n-2) $

$ f(n-1) = f(n-1) +f(n-2) $

     $ \vdots $

$ f(2) = f(1) + f(0) $

$ f(1) = 1 $

$ f(0) = 1 $

따라서 점화식은

 $ f(n) = \begin{cases}1 & (n<1) \\ f(n-1) + f(n-2) & (n > 1)\end{cases} $이고

이를 행렬로 나타내 보면

$ \begin{bmatrix}f(n+1) & f(n) \\f(n) & f(n-1) \end{bmatrix} =  \begin{bmatrix}1 & 1 \\1 & 0 \end{bmatrix} ^{n}  $

즉, $  \begin{bmatrix}1 & 1 \\1 & 0 \end{bmatrix}  $의 거듭제곱으로 구할 수 있다는 것을 알 수 있다.

구현하는 방법은 이전 문제에서 해봤기 때문에 너무나도 쉽게 구현해주면 된다.

구현하는 것이 어려운 분들은 https://www.acmicpc.net/problem/10830 해당 링크에 가면 이해할 수 있을 것이다.