Cometin'

BOJ-11444 - Python

2021-06-28 at Algorithm category

최대 10경 번째 피보나치 수를 구하는 문제. 첫 번째 풀이는 두 개의 변수에 값을 할당하는 방식으로 풀었으나 당연하게도 시간초과 결과를 받게 되었다. 검색하여 알아본 결과 매우 매우 큰 수의 피보나치를 빠르게 구하는 방법은 행렬의 거듭제곱을 사용한다고 한다. 위 링크의 게시물을 참고하여 풀었으나 아직 많이 부족하다.

# n = int(input())
# x, y = 0, 1
# for _ in range(n):
#     x, y = y, (x+y) % 1000000007
# print(x)


def power(adj, n):
    if n == 1: return adj
    elif n % 2: return multi(power(adj, n-1), adj)
    else: return power(multi(adj, adj), n // 2)


def multi(a, b):
    temp = [[0] * len(b[0]) for _ in range(2)]
    for i in range(2):
        for j in range(len(b[0])):
            sum_n = 0
            for k in range(2):
                sum_n += a[i][k] * b[k][j]
            temp[i][j] = sum_n % MOD

    return temp


MOD = 1000000007
adj = [[1, 1], [1, 0]]
start = [[1], [1]]
N = int(input())

print(1 if N < 3 else multi(power(adj, N-2), start)[0][0])

hyesungoh

Personal blog by hyesungoh.

I like to share my knowledge for those who wandering in issue.