[백준] 10830 행렬 제곱 (파이썬 python)

 

 

문제 링크

 

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

10830번: 행렬 제곱

 

 

문제 풀이

 

주어진 조건에서 B의 크기가 매우 크기 때문에 단순히 구현을 할 경우 시간 초과가 난다.

이럴 경우 연산을 쪼개는 분할 정복 알고리즘을 활용해야 한다.

 

def square(matrix, n):
    if n == 1:
        return matrix
    temp = square(matrix, n // 2)
    if n % 2 == 0 :
        return multi(temp, temp)
    else :
        return multi(multi(temp, temp), matrix)

 

B가 짝수일 경우 A^B는 (A^(B//2)) * (A^(B//2))와 같고

홀수일 경우 (A^(B//2)) * (A^(B//2)) * A와 같다.

이렇게 수를 줄여나가며 시간복잡도를 줄이는 방법이다.

 

또한 매 연산마다 1000을 나눈 나머지값으로 대입하여

연산에 사용되는 숫자를 줄이면 시간 복잡도를 보다 작게 만들 수 있다.

 

import sys
input = sys.stdin.readline

def multi(mat1, mat2):
    res_mat = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                res_mat[i][j] += mat1[i][k] * mat2[k][j] % 1000
    return res_mat

def square(matrix, n):
    if n == 1:
        return matrix
    temp = square(matrix, n // 2)
    if n % 2 == 0 :
        return multi(temp, temp)
    else :
        return multi(multi(temp, temp), matrix)

n, b = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
result = square(a, b)
for row in result:
    for num in row:
        print(num % 1000, end=' ')
    print()