[분할정복] 백준 - 행렬 곱셈 10830번

행렬 곱셈 10830번

😘 문제 요약

A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

👏 key point

이때 제곱의 크기를 나타내는 B의 크기가 1 ≤ B ≤ 100,000,000,000이다. 따라서 단순하게 행렬의 곱셈을 하였다가는 시간초과가 걸릴 것이다. 그렇다면 시간을 단축시키면서 행렬의 곱셈을 구할 수 있는 효과적인 방법은 무엇인가???

바로 분할 정복이다.

위의 그림과 같은 원리로 홀수이면 -1을 하고 짝수일 경우 // 2를 하여 분해를 한다. 병합을 할 경우 1부터 순서대로 다시 병합한다.

1 - > 2 (1제곱의 행렬을 두개 곱하여서) -> 3(1제곱의 행렬과 2제곱의 행렬을 두개를 곱하여서) -> ...

🎂 코드

n,m = map(int, input().split())

mat = []

for _ in range(n):
    mat.append(list(map(int, input().split())))

def mul(M,k):
    # k크기가 1이 될 때까지 분할
    if k == 1:
        for i in range(n):
            for j in range(n):
                M[i][j] = M[i][j] % 1000
        return M
    
    elif k % 2 == 0:
        graph = [[0]*n for _ in range(n)]
        #짝수일 경우 // 2로 분할
        C = mul(M,k // 2)
        # 병합
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    graph[i][j] += C[i][k]*C[k][j]
                graph[i][j] %= 1000
        
        return graph

    
    elif k % 2 == 1:
        graph = [[0]*n for _ in range(n)]
        #홀수 일 경우 -1로 분할
        C = mul(M,k-1)
        #병합
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    graph[i][j] += C[i][k]*M[k][j]

                graph[i][j] %= 1000

        return graph

result = mul(mat,m)

for i in result:
    for j in i:
        print(j,end = " ")
    print()