[백준] 행렬 제곱

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

10830번: 행렬 제곱

분할정복을 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

N*N의 행렬과 이것을 몇제곱 할지가 주어지면, 행렬을 해당하는 만큼 제곱한 결과를 return해야 합니다. 

 

<Solution>

거듭제곱에 대한 이야기는 이전 여러 문제들에서 분할정복 방식으로 해결한 적이 있습니다. 

https://life318.tistory.com/61

[백준] 곱셈

https://life318.tistory.com/22

[백준] 이항 계수 3(페르마 소정리, modular inverse, 분할정복)

 

간단하게 자연수에 대해 생각해봅시다. 만약 2^100을 구한다고 생각하면 

 

2^100 -> 2^50 * 2^50

2^50 -> 2^25 * 2^25

2^25 -> 2^12 * 2^12 *2

.....

 

이러한 방식으로 지수 부분을 2로 나눈 값을 먼저 구하고 이것을 제곱하는 방식으로 문제를 해결할 수 있습니다.

 

행렬 또한 마찬가지로 똑같은 방식으로 해결이 가능합니다. 

이를 위해 행렬을 곱하는 함수를 만들었고 기존에 만들어 두었던 분할정복을 이용한 거듭제곱 함수를 변형 시켜서 문제를 해결하였습니다. 

https://life318.tistory.com/62

거듭제곱 분할정복

 

행렬을 곱하는 것은 numpy같은 라이브러리를 사용할 수 없으므로 map과 zip을 적절히 활용하면 크게 어렵지 않게 구현할 수 있습니다. 

 

실제 구현은 아래와 같습니다.

import sys

N , B = list(map(int,sys.stdin.readline().rstrip().split()))

def multiple_matrix(A,B):
    # find dimension (row -> m, column -> n)
    m_A = len(A)
    n_A = len(A[0])
    m_B = len(B)
    n_B = len(B[0])
    assert(m_A == n_B and n_A == m_B)
    # return matrix
    return_matrix = [[] for _ in range(m_A)]
    tmp = list(zip(*B))

    for i in range(m_A):
        for j in range(n_B):
            return_matrix[i].append(sum(map(lambda x : x[0] * x[1], zip(A[i], tmp[j]))) % 1000)
    return return_matrix

def exp(base, expo):
    if expo == 1:
        n_base = []
        for row in base:
            n_base.append(list(map(lambda x: x%1000, row)))
        return n_base
    a = exp(base, expo//2)
    b = expo%2
    
    if b == 0: 
        return multiple_matrix(a,a)
    else: # b ==1
        return multiple_matrix(multiple_matrix(a,a),base)

# build matrix
matrix = []
for _ in range(N):
    matrix.append(list(map(int, sys.stdin.readline().rstrip().split())))

return_matrix = exp(matrix, B)

for row in return_matrix:
    n_row = list(map(str, row))
    print(' '.join(n_row))