[알고리즘][Python] 백준 10830 행렬 제곱 문제 풀이

문제 출처 : www.acmicpc.net/problem/10830

10830번: 행렬 제곱

---

문제 해석 : 행렬 제곱을 수행하는 문제이다. 행렬 A와 제곱하는 횟수 B가 주어지면 행렬의 곱을 B번 반복하면 된다.

 

문제 풀이 : 100,000,000,000까지 제곱을 수행하기 때문에 일반적인 행렬의 제곱으로는 (N^3)의 곱셈 * 100,000,000,000을 수행하면 시간 초과나 난다. 따라서 A^16 같은 경우 A^2^2^2^2으로 연산해야한다. 이렇게 되면 밑이 2인 로그만큼으로 연산 횟수가 줄기 때문에 주어진 시간 내로 연산을 완료할 수 있다.

---

풀이 코드

def multiply(arr, B):

    if B == 1:
        for i in range(N):
            for j in range(N):
                arr[i][j] %= 1000
        return arr

    elif B % 2 == 1:

        arr2 = multiply(arr, B-1)
        result = []

        for i in range(N):
            temp = []
            for j in range(N):
                summ = 0
                for k in range(N):
                    row = arr2[i][k]
                    col = arr[k][j]
                    summ += row * col

                temp.append(summ % 1000)
            result.append(temp)

        return result

    else:

        arr2 = multiply(arr, B//2)
        result = []

        for i in range(N):
            temp = []

            for j in range(N):
                summ = 0

                for k in range(N):
                    row = arr2[i][k]
                    col = arr2[k][j]
                    summ += row * col

                temp.append(summ % 1000)
            result.append(temp)

        return result

import sys
input = sys.stdin.readline

N, B = map(int, input().split())

arr_ori = [list(map(int, input().split())) for _ in range(N)]

answer = multiply(arr_ori, B)

for i in range(N):
    for j in range(N):
        print(answer[i][j], end = " ")
    print()

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.