#354 백준 파이썬 [2749] 피보나치 수 3

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

 

SOLUTION

행렬을 이용한 방법으로 빠르게 피보나치 수를 구해주었다.

설명하기 너무 길다...

백준님과(https://www.acmicpc.net/blog/view/28) 

Parkito님(https://shoark7.github.io/programming/algorithm/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84-%ED%95%B4%EA%B2%B0%ED%95%98%EB%8A%94-5%EA%B0%80%EC%A7%80-%EB%B0%A9%EB%B2%95.html)

이 굉장히 잘 설명해주셨다.

따라해보자.

 

요약하자면 원리는 다음과 같다.

n을 이진법으로 바꿔준다.

10101(2)를 피보나치 수를 행렬로 표현하면

[[fn , fn-1 ], [fn-1 , fn-2]]

= [[1, 1], [1, 0]] ^ 2 ^ 4

* [[1, 1], [1, 0]] ^ 2 ^ 2

* [[1, 1], [1, 0]] ^ 2 ^ 0

과 같다.

PYTHON CODE

#2^x 피보나치를 구해주는 함수
def matrix_mul_self(x):
    base = [[1, 1], [1, 0]]
    result = [[1, 1], [1, 0]]
    for _ in range(x):
        result = [[0, 0], [0, 0]]
        for i in range(2):
            for j in range(2):
                for k in range(2):
                    result[i][j] += (base[i][k] * base[k][j]) % 1000000
        base = result
        
    return result

#2*2 두 행렬의 곱을 구해주는 함수
def matrix_mul(a, b):
    result = [[0 ,0], [0, 0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                result[i][j] += (a[i][k] * b[k][j]) % 1000000
                
    return result

n = bin(int(input()))[2:] #2진법으로 변환

result = [[1, 0], [0, 1]]
for i in range(len(n)):
    if n[-i-1] == '1': #2^x 피보나치들만 구해준 다음 곱해줌
        result = matrix_mul(result, matrix_mul_self(i))
        
print(result[0][1] % 1000000)