백준 10830 행렬 제곱 파이썬

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

 

예제 입력	예제 출력
2 5 1 2 3 4	69 558 337 406
3 3 1 2 3 4 5 6 7 8 9	468 576 684 62 305 548 656 34 412
5 10 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1	512 0 0 0 512 512 0 0 0 512 512 0 0 0 512 512 0 0 0 512 512 0 0 0 512

 

문제 바로가기

---

이 문제를 풀기 전에 백준 곱셈 문제를 풀고 오시는 것을 추천합니다.

 

분할 정복

1. Divide : 원하는 크기의 문제로 분할
2. Conquer : 나눈 문제를 하나씩 정복해나감
3. Combine : 푼 문제의 답들을 하나로 결합

 

코드 구현

행렬을 제곱해야 하는데, 제곱할 횟수가 크면 값도 커지므로 계산이 오래 걸립니다. 그래서 제곱할 횟수를 나눠 계산하는 분할 정복을 적용했습니다. 행렬을 곱할 때마다 1000을 나누어 나머지가 값이 되도록 하면, 가지고 다니는 값 자체가 작아지기도 하고 계산 횟수도 줄일 수 있어 계산이 비교적 빨라집니다.

 

계산 횟수가 작아지는 이유

만약 (3^64)이라면 3를 64번 곱해야 함으로 64번을 계산해야 하지만, ((3^32)^2)이라면 32번 곱한 것을 한번만 더 곱하면 됨으로 총 33번 만에 계산할 수 있습니다.

 

Multiple 함수

두 행렬을 곱하는 함수입니다. 먼저 결과 행렬을 저장할 result 변수를 선언합니다. 두 행렬을 곱해 result에 누적하여 더해준 후, 각 계산이 끝날 때마다 1000을 나눈 나머지를 저장합니다.

for i in range(size):
    for j in range(size):
        for k in range(size):
            result[i][j] += matrix1[i][k] * matrix2[k][j]
        result[i][j] %= 1000

 

Divide 함수

곱하는 횟수를 나눠 계산할 수 있도록 하는 함수입니다. 즉, 곱하는 횟수를 분할 정복하여 푸는 방법입니다.  곱하는 횟수가 짝수일 때와 홀수일 때를 나눠 계산합니다. 곱셈 문제와 마찬가지로,  분배 법칙을 이용하여 계산합니다.

if cnt % 2 == 0:
    return multiple(size, tmp, tmp)
else:
    return multiple(size, multiple(size, tmp, tmp), matrix)

 

분배 법칙

(a * b) % c = ((a % c) * (b % c)) %c

 

전체 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000)

# 행렬의 크기, 제곱할 횟수
n, b = map(int, input().split())
numbers = [list(map(int, input().split())) for _ in range(n)]

def multiple(size, matrix1, matrix2):
    result = [[0] * n for _ in range(size)]
    # result = [[0 for _ in range(size)] for _ in range(size)]

    for i in range(size):
        for j in range(size):
            for k in range(size):
                result[i][j] += matrix1[i][k] * matrix2[k][j]
            result[i][j] %= 1000
    
    return result

def divide(size, cnt, matrix):
    if cnt == 1:
        return matrix
    else:
        tmp = divide(size, cnt//2, matrix)

        if cnt % 2 == 0:
            return multiple(size, tmp, tmp)
        else:
            return multiple(size, multiple(size, tmp, tmp), matrix)
        
results = divide(n, b, numbers)

for result in results:
    for num in result:
        print(num % 1000, end = ' ')
    print()