문제/백준_파이썬
170. 10830(행렬 제곱) - 파이썬
sm_hope
2022. 8. 4. 22:44
import sys
input = sys.stdin.readline
# 행렬 곱을 처리하는 부분
def MatrixMul(A, B):
N = len(A)
C = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
for j in range(N):
for k in range(N):
C[i][j] += A[i][k] * B[k][j]
remainder(C)
return C
# 1000으로 나눈 나머지를 구하는 부분
def remainder(A):
N = len(A)
for i in range(N):
for j in range(N):
A[i][j] %= 1000
# 거듭 제곱을 분할정복으로 하는 부분
def pow(A, B):
if B == 1:
return A
tmp = pow(A, B//2)
if B % 2 == 1:
return MatrixMul(MatrixMul(tmp, tmp), A)
else:
return MatrixMul(tmp, tmp)
N, B = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
remainder(A) # 들어온 값들이 1000보다 클 수 있므로 나눔.
result = pow(A, B)
for val in result:
print(*val)
문제요약
행렬 곱을 진행하라(분할정복을 이용해서)
설명
먼저 행렬의 곱셈은 다음으로 나타낼 수 있다.
제곱은 다음으로 나타낼 수 있다.
따라서 행렬의 곱셈은
def MatrixMul(A, B):
N = len(A)
C = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
for j in range(N):
for k in range(N):
C[i][j] += A[i][k] * B[k][j]
remainder(C)
return C
위와 같이 표현했다.
remailder는 1000의 나머지를 구하기 위해 사용해 준 것이다.
때문에 다음과 같이 나타낼 수 있다.
def remainder(A):
N = len(A)
for i in range(N):
for j in range(N):
A[i][j] %= 1000
거듭제곱 또한 위에서 나타낸거 같이
def pow(A, B):
if B == 1:
return A
tmp = pow(A, B//2)
if B % 2 == 1:
return MatrixMul(MatrixMul(tmp, tmp), A)
else:
return MatrixMul(tmp, tmp)
이런식으로 코드를 짤 수 있고, 분할 정복 단계에서 거듭제곱은 많이 다뤘기 때문에 이해는데 어렵지 않을 것이다.
※입력이 1000보다 클 수 있다.
따라서 먼저 remainder를 실행하고 계산을 진행 하는 것이 좋다.
remainder(A) # 들어온 값들이 1000보다 클 수 있므로 나눔.