백준 11444번: 피보나치 수 6 (Graph, Matrix)

문제링크:11444번: 피보나치 수 6 (acmicpc.net)

11444번: 피보나치 수 6

피보나치 수는 알다시피 점화식이 Fn=Fn-1+Fn-2 로 표현될 수 있다. 그렇다면 N번째 피보나치 수를 구하려면 반드시 0부터 N까지 더해가며 An을 구해야 할까? 나도 처음에 그래야 할 것이라고 생각했지만 답은 아니었다. 답은 행렬의 곱셈을 이용하여 N번째 피보나치 수의 일반항을 구할 수 있다.

 

 

위 식을 보면 행렬 [[Fn],[Fn-1]] 행렬에 행렬 [[1,1],[1,0]]을 곱하면 각각 다음 피보나치 수가 나오는 것을 알 수 있다. 이는 행렬의 곱셈 과정 중 1행에는 (1*Fn)+(1*Fn-1) 이 남고, 2행에는 (1*F*n)+(0*Fn-1) 가 남기 때문에 1행은 Fn+1이 남고 2행은 Fn이 남게 된다. 그렇다면 만약 피보나치 0번항, 1번항에 행렬[[1,1],[1,0]]을 i번 곱한다면 아래와 같은 모양이 될 것이다.

 

 

이렇게 해서 우리는 피보나치 수의 일반항을 구할 수 있다. 행렬의 제곱 연산을 분할 정복을 통해 구한다면, 시간 내에 답을 구할 수 있다.

 

import sys
N=int(sys.stdin.readline().rstrip())

mod=1000000007

fibo=[[1,1],[1,0]]

def matpower(mat,n):
    
    sqrmat=[[0 for _ in range(2)] for _ in range(2)]
    if n==0:
        return [[0,0],[0,0]]
    if n==1:
        for i in range(2):
            for j in range(2):
                sqrmat[i][j]=mat[i][j]%mod
        return sqrmat
    
    if n%2==0:
        for i in range(2):
            for j in range(2):
                val=0
                for k in range(2):
                    A=mat[i][k]
                    B=mat[k][j]
                    val+=A*B
                    sqrmat[i][j]=val%mod  
        return matpower(sqrmat,n//2)
    else:
        for i in range(2):
            for j in range(2):
                sqrmat[i][j]=mat[i][j]%mod
        return matmult(matpower(sqrmat,n-1),sqrmat)

def matmult(mat1,mat2):
    multmat=[[0 for _ in range(2)] for _ in range(2)]
    for i in range(2):
        for j in range(2):
            val=0
            for k in range(2):
                A=mat1[i][k]
                B=mat2[k][j]
                val+=A*B
            multmat[i][j]=val%mod
    return multmat

if N==0:
    print(0)
elif N==1:
    print(1)
else:
    print(matpower(fibo,N-1)[0][0])

점화식이 덧셈으로 이루어져 있는 특징을 이용해 행렬 곱셈을 통해 일반항을 구할 수 있었다. 행렬 곱셈에 아직 익숙하지 않지만 점화식의 일반항을 빠르게 구하는 데에 사용 될 수 있을 것 같다.