#Algorithm
문제 번호
10830(G4)
알고리즘 + 이론
분할 정복 알고리즘
거듭제곱에서 그대로 n번 제곱하는 것이 아니라 분할하여 2의 거듭제곱으로 분할한 수만큼 여러번 곱하면서 $log_{2}n$번 곱하게 바꿀 수 있음
정답 코드
# 10830번
N, B = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
result = [[0] * N for _ in range(N)]
for i in range(N):
result[i][i] = 1
for j in range(N):
A[i][j] %= 1000
while B > 0:
if B % 2 == 1:
temp = [[0] * N for _ in range(N)]
for i in range(N):
for j in range(N):
for k in range(N):
temp[i][j] += result[i][k] * A[k][j]
temp[i][j] %= 1000
result = temp
temp = [[0] * N for _ in range(N)]
for i in range(N):
for j in range(N):
for k in range(N):
temp[i][j] += A[i][k] * A[k][j]
temp[i][j] %= 1000
A = temp
B //= 2
for row in result:
print(' '.join(map(str, row)))
느낀점 & 피드백
2의 거듭제곱으로 분할하는 아이디어를 떠올리기 어려워서 거듭제곱 분할 정복 알고리즘을 참고했고 그 뒤에 단위 행렬로 result 초기화 부분도 생각치 못해서 한 번 틀리고 고쳤다.
이 글이 도움이 되셨나요?