[CLASS 4]백준 10830번 - 행렬 제곱

10830번 - 행렬 제곱

 

수학적 지식, 그중에서도 행렬에 대한 지식이 좀 필요한 문제이다. 먼저 행렬 곱의 과정에 대하여 알고 이를 구현할 수 있어야 하고, 푸는 방식에 따라 단위 행렬도 사용해야 한다.

 

그것들을 다 알고 있다면 꽤 익숙하고 유명한 분할 정복을 이용한 거듭제곱 문제이다. 컴퓨터는 2^16을 구한다고 할 때, 그냥 2를 16번 곱하는 것보다 (((2^2)^2)^2)^2 의 방식으로 구하는 것이 속도가 더 빠르다. 이를 이용하면 거듭제곱에서 O(n)을 O(logn)으로 획기적으로 줄일 수 있다.

 

내 코드:

# dawitblog.tistory.com/161
from sys import stdin
input = stdin.readline

# 행렬 곱셈
def mat_multi(a,b):
    temp = [[0]*size for _ in range(size)]

    for r in range(size):
        for c in range(size):
            for k in range(size):
                temp[r][c] += a[r][k] * b[k][c]

    for r in range(size):
        for c in range(size):
            temp[r][c] %= 1000

    return temp


size, count = map(int,input().split())
mat = []
for _ in range(size):
    mat.append(list(map(int,input().split())))

# 단위 행렬
ans_mat = [[int(r==c) for c in range(size)] for r in range(size)]

# 분할 정복
while count != 1:
    if count % 2:
        ans_mat = mat_multi(ans_mat,mat)
        count -= 1
    else:
        mat = mat_multi(mat,mat)
        count //= 2

ans_mat = mat_multi(ans_mat,mat)
# 출력
for line in ans_mat:
    print(*line)

 

행렬 곱셈 구현하는게 제일 어려웠던 것 같다. 행렬 너무 오랜만에 써봐서...

 

행렬 곱셈 함수를 제대로 구현하였다면 그 다음은 조금 헷갈릴 수는 있어도 어렵지 않다. 규칙에 따라 분할 정복하면 된다.

 

• 남은 지수가 홀수(count%2 == 1)라면 ans_mat에 mat 곱하기
• 남은 지수가 짝수(count%2 == 0)라면 mat에 mat 곱하기

이렇게 지수가 1이 될때까지 시행한 후 ans_mat에 mat 을 한번 곱해주면 답이 나온다.