#Algorithm
문제 번호
11444번(G2)
알고리즘 + 이론
분할정복 알고리즘
행렬곱의 분할정복 알고리즘 응용이다.
피보나치 수열은 사실 행렬곱으로 쉽게 구할 수 있는데 그것은 $[[1,1],[1,0]]^n$ * $[[F_{1}],[F_{0}]]$ 은 $[[F_{n+1}],[F_{n}]]$이라는 사실을 이용하면 됩니다. 암기할게요.
정답 코드
# 11444번
import sys
N = int(input())
if N == 0:
print(0)
sys.exit(0)
A = [[1,1],[1,0]]
result = [[1,0],[0,1]]
while N > 0:
if N % 2 == 1:
temp = [[0] * 2 for _ in range(2)]
for i in range(2):
for j in range(2):
for k in range(2):
temp[i][j] += result[i][k] * A[k][j]
temp[i][j] %= 1000000007
result = temp
temp = [[0] * 2 for _ in range(2)]
for i in range(2):
for j in range(2):
for k in range(2):
temp[i][j] += A[i][k] * A[k][j]
temp[i][j] %= 1000000007
A = temp
N //= 2
else:
print(result[1][0] % 1000000007)
느낀점 & 피드백
이렇게 풀어보면서 푸는 방법을 암기하는 게 맞다는 생각이 든다.
이 글이 도움이 되셨나요?