백준 - 행렬 곱셈 10830번
😘 문제 요약
A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.
👏 key point
이때 제곱의 크기를 나타내는 B의 크기가 1 ≤ B ≤ 100,000,000,000이다. 따라서 단순하게 행렬의 곱셈을 하였다가는 시간초과가 걸릴 것이다. 그렇다면 시간을 단축시키면서 행렬의 곱셈을 구할 수 있는 효과적인 방법은 무엇인가???
바로 분할 정복이다.
위의 그림과 같은 원리로 홀수이면 -1을 하고 짝수일 경우 // 2를 하여 분해를 한다. 병합을 할 경우 1부터 순서대로 다시 병합한다.
1 - > 2 (1제곱의 행렬을 두개 곱하여서) -> 3(1제곱의 행렬과 2제곱의 행렬을 두개를 곱하여서) -> ...
🎂 코드
n,m = map(int, input().split())
mat = []
for _ in range(n):
mat.append(list(map(int, input().split())))
def mul(M,k):
# k크기가 1이 될 때까지 분할
if k == 1:
for i in range(n):
for j in range(n):
M[i][j] = M[i][j] % 1000
return M
elif k % 2 == 0:
graph = [[0]*n for _ in range(n)]
#짝수일 경우 // 2로 분할
C = mul(M,k // 2)
# 병합
for i in range(n):
for j in range(n):
for k in range(n):
graph[i][j] += C[i][k]*C[k][j]
graph[i][j] %= 1000
return graph
elif k % 2 == 1:
graph = [[0]*n for _ in range(n)]
#홀수 일 경우 -1로 분할
C = mul(M,k-1)
#병합
for i in range(n):
for j in range(n):
for k in range(n):
graph[i][j] += C[i][k]*M[k][j]
graph[i][j] %= 1000
return graph
result = mul(mat,m)
for i in result:
for j in i:
print(j,end = " ")
print()
Author And Source
이 문제에 관하여(백준 - 행렬 곱셈 10830번), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@turtle601/백준-행렬-곱셈-10830번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)