[백준(파이썬/Python)] 10830_행렬 제곱

https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱

 

행렬 거듭제곱의 연산 수가 100,000,000,000까지 갈 수 있기 때문에 일일이 계산하는 것은 불가능한 문제입니다.

 

따라서 분할 정복 개념을 바탕으로 거듭제곱근으로 나눠나가는 아이디어를 떠올려야 합니다. 예를 들어 A^100 = A^50 * A^50이고, A^5 = A^2 * A^2 * A처럼 차수를 2의 제곱근으로 떨어뜨릴 수 있는 것이죠.

 

한편, 행렬의 곱셈 연산은 multyplyMatrix(m1, m2)에서 정의해놓은 것처럼 구현할 수 있는데 처음에 바로 떠오르지 않아서 종이에 3*3 행렬의 곱셈을 풀어서 써보고 구현했습니다.

 

재귀적 연산에서는 거듭제곱수가 짝수일 때 그 절반으로 나누어 재귀 연산을 수행한 결과값에 마지막으로 A^2을 해주면 되고, 홀수일 때는 제곱수에서 하나를 뺀 녀석(이제 거듭제곱수는 짝수)을 재귀 수행한 결과에 마지막으로 A를 곱해주면 됩니다. 위에서 말한 내용을 조금 풀어서 종이에 써보면 아마 이해될 것 같습니다...ㅎㅎ

 

그런데, 이 로직을 그대로 따라가도 시간초과가 발생하는데, 이를 해결하기 위해서는 multiplyMatrix()안에 있는 것처럼 매 곱셈마다 행렬의 수를 1000으로 나눠줘야만 합니다. 그렇지 않으면 매우 큰 수의 연산을 하는 데 드는 시간으로 인해 시간초과가 발생할 수 있습니다.

 

[풀이]

import sys

def multiplyMatrix(m1, m2):
    length = len(m1)
    result = [[0] * length for _ in range(length)]
    for i in range(length):
        for j in range(length):
            for k in range(length):
                result[i][j] += m1[i][k] * m2[k][j]
                # 1000으로 나눠주면서 큰 수 연산을 줄인다.
                result[i][j] %= 1000
    return result

def recursivelyMultiplying(matrix, b):
    if b == 1:
        return matrix
    else:
        if b % 2 == 0:
            matrix = recursivelyMultiplying(matrix, b // 2)
            return multiplyMatrix(matrix, matrix)

        else:
            matrix = recursivelyMultiplying(matrix, b-1)
            return multiplyMatrix(initial_matrix, matrix)

n, b = map(int, sys.stdin.readline().split())
initial_matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
result_matrix = recursivelyMultiplying(initial_matrix, b)
for i in range(n):
    for j in range(n):
        print(result_matrix[i][j] % 1000, end = ' ')
    print()