[Python] 백준 - 10830 행렬 제곱

문제

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

입력

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤  5, 1 ≤ B ≤ 100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

 
 

문제해결방법

 
 
1. 행렬 제곱은 같은 행렬을 곱셈해주면 된다. 행렬 곱셈의 경우 A(n x m)행렬의 열인 m 과 B(m x k)행렬의 행인 m이 같아야 계산 가능하다. 행렬 제곱은 행과 열이 동일해야만 가능하다.
 
 

[Python] 백준 - 2740 행렬 곱셈

- 행렬 곱셈하는 방법 포스팅
 
 
2. 여러 번 거듭 제곱을 해야 하는데, 그 횟수만큼 곱셈을 하면 행렬의 숫자가 매우 커질 것을 예상할 수 있다.  100,000,000,000번 제곱을 해야할 수도 있다고 한다. 행렬 곱셈의 코드가 3중 for문으로 작동하니,  $O(n^{3})$ x 100,000,000,000의 시간이 걸릴 수도 있다. 분할정복을 이용해서 거듭제곱을 줄여야 한다. (거듭제곱부분을 $ O(logB)$까지 줄일 수 있다.)
 
 

<거듭 제곱은 이런 식으로 분할되어, 시간복잡도가 $ O(logB)$로 줄어든다.>

 
※ 지수가 크지 않을 때는, 연산 횟수 차이가 얼마 나지 않아도, 지수가 커질 때는 큰 차이가 나게 된다. 이 pow함수에 행렬 곱셈 함수를 합성한다. 지수가 홀수일 때는 마지막에 한번만 더 곱해주면 된다.
 
3. 나머지 연산도 계속 해준다.
 
 
 

- 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, b = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]

for i in range(n):
    for j in range(n):
        A[i][j] %= 1000

def mul(a, b):
    res = [[0 for _ in range(len(b))] for _ in range(len(a))]
    for i in range(n):
        for j in range(n):
            temp = 0
            for k in range(n):
                temp += a[i][k] * b[k][j]
            res[i][j] = temp % 1000
    return res

def pow(a, b):
    if b == 1:
        return a
    else:
        temp = pow(a, b//2)
        if b % 2 == 0:
            return mul(temp, temp)
        else:
            return mul(mul(temp, temp), a)

for i in pow(A, b):
    print(*i)