boj 11444

“https://www.acmicpc.net/problem/11444”

from sys import stdin

def pibo(n):
    if n<=1:
        return init
    else:
        temp = pibo(n//2) ## key point --> 어떠한 함수를 부르는 연산은 미리 변수 선언을 해놓고 그 변수를 부르는것이 시간적으로 단축 가능!!
        if n%2 == 0:
            return SumOfProduct( temp, temp)
        else:
            return SumOfProduct( init, SumOfProduct(temp, temp))

def SumOfProduct(matrix1, matrix2):
    
    ans = [[0] * 2 for _ in range(2)]
    ans[0][0] = (matrix1[0][0] * matrix2[0][0] + matrix1[0][1] * matrix2[1][0])%1000000007
    ans[0][1] = (matrix1[0][0] * matrix2[0][1] + matrix1[0][1] * matrix2[1][1])%1000000007
    ans[1][0] = (matrix1[1][0] * matrix2[0][0] + matrix1[1][1] * matrix2[1][0])%1000000007
    ans[1][1] = (matrix1[1][0] * matrix2[0][1] + matrix1[1][1] * matrix2[1][1])%1000000007

    return ans
    
if __name__ == "__main__":
    num = int(stdin.readline())
    init = [[0,1],[1,1]]
    if num == 0:
        print("0")
    else:
        print(pibo(num)[0][1])

notion

• 피보나치 수열을 재귀방식이 아닌 분할정복으로 푼다.
• [[0,1][1,1]]행렬의 제곱을 이용하여 피보나치 수열을 구할 수 있다 --> 가장 빠른 방법이다.
• 어떠한 함수를 부르는 연산은 미리 변수에 할당 시켜놓고 변수를 가져와서 사용하는 것이 시간 단축!!!