[Python]분할정복 백준 2749

   문제

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

n의 크기가 무지막지하다.주어진 n의 크기는 0의 숫자 조차 세기 힘들다.

메모이제이션은 O(n)이라는 시간이 걸린다. 보통의 풀이방식으로는 불가능하다

피보나치 수열을 분할정복으로 풀 수 있는 방법이 있다는건데 찾아봐야겟다...

https://www.acmicpc.net/blog/view/28

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

행렬을 통해 피보나치수열을 구할수 있다는것과 일반항으로도 표현할수 있다는것에

 놀랐다. 굉장히 많은것을 배울수 있었다.

앞서 사용했던 행렬의 제곱을 이용하여 구하였다.

다음에기회가 된다면 일반항을 통해 구현해 봐야겠다.

def fibo_matric(A,n):
 
    if n==1:
        for i in range(2):
            for j in range(2):
                A[i][j]%=1000000
        return A
    elif n%2==1:
        tmp = [[0, 0], [0, 0]]
        B=fibo_matric(A,n-1)
        for i in range(2):
            for j in range(2):
                for k in range(2):
                    tmp[i][j] += B[i][k] * A[k][j]
                tmp[i][j] %= 1000000
        return tmp
    else:
        tmp = [[0, 0], [0, 0]]
        B = fibo_matric(A, n//2)
        for i in range(2):
            for j in range(2):
                for k in range(2):
                    tmp[i][j] += B[i][k] * B[k][j]
                tmp[i][j] %= 1000000
        return tmp
 
 
n=int(input())
A=[[1,1],[1,0]]
if n==0:
    print(0)
elif n==1:
    print(1)
else:
    print(fibo_matric(A,n-1)[0][0])