파이썬 백준 2749 피보나치 수 3

n = int(input()) bilist = [] while n != 0 :     bilist.append(n%2)     n = n//2 def mult(A, B) :     C = [[0 for i in range(2)] for j in range(2)]     for i in range(2) :         for j in range(2) :             sum = 0             for x in range(2) :                 sum = sum + A[i][x] * B[x][j]             C[i][j] = sum % 1000000     return C X = [[1, 1], [1, 0]] powerlist = [] for i in range(len(bilist)) :     powerlist.append(X)     X = mult(X, X) Xn = [[1,0],[0,1]] for i in range(len(bilist)) :     if bilist[i] == 1 :         Xn = mult(Xn, powerlist[i]) print(Xn[0][1])

1주차에 피보나치 수 2까지 풀어보고 3을 시간초과로 못풀었는데,

이번 주차에 분할정복과 a^b 구하기를 해보니 풀 수 있게 되었다.

피보나치 점화식 a_n+1 = a_n + a_n-1 과 a_n = a_n이라는 항등식을 합쳐 벡터의 꼴로 나타내면,

[a_n+1, a_n] = [(1,1), (1,0)] * [a_n, a_n-1]이라는 벡터 점화식이 나온다.

즉 [a_n+1, a_n]는 [(1,1), (1,0)]의 n승에 [a_1, a_0] (= [1, 0])을 곱한 것과 같다.

행렬의 거듭제곱은 10830 행렬 제곱(https://uneducatedjungler.tistory.com/25)에서 구현했으므로,

이를 이용하여 [(1,1), (1,0)]^n을 구하고 [1, 0]과 곱해준 것의 오른쪽 원소를 구하면 a_n이 나온다.

 

코치님이 초반에는 어차피 아는게 없으니 길게 고민 말고 남의 코드를 흡수하며 지식을 넓히라는 말씀을 하셨는데

풀어본 문제들의 조합으로 비슷한 난이도의 새 문제를 쉽게 푸는 상황이 되니 어느정도 이해가 된다.