[백준/10830/파이썬] 행렬 제곱

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

10830번: 행렬 제곱

Problem

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

조건

• 첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤  5, 1 ≤ B ≤ 100,000,000,000)
• 둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.
• 첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

SOL

 

행렬의 곱셈

행렬, 고등학교때, 행렬이 고등 교과과정에서 빠져서, 대학교가서 고생하면서 배웠다. :(

행렬의 곱셈은 순서가 있고, 조건도 있다! 

 

물론, 이 순서와 조건에는 이유가 있다.(수학에 이유가 없는건 없다)

하지만, 그건 행렬의 곱셈 조건이라고 구글에치면 아주 자세하게 잘 나오기 때문에,  곱셈의 순서만 간단하게 언급하고 넘어가겠음! 숫자로 예를 들면, 아래와 같은 순서를 따르게 된다. (1행 1열 = 1행 1열 * 1행 1열 +1행 2열 *2행 1열 ...)

 

행과 열을 번갈아가면서 곱한다면, 느낌이 확 올거다! 

컴퓨터로 구현은 다양한 방법이 있지만, 간단한 방법으로는 3중반복을 도는거다!

def mul(matrix1,matrix2):
    ans=[[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                ans[i][j] += matrix1[i][k]*matrix2[k][j]
            ans[i][j] %=1000
    return ans

자기 자신을 계속 제곱하는거이므로, 행렬의 곱셈 조건은 당연히 만족하고, 거듭제곱을 빠르게 구현하는 아이디어처럼, 행렬 제곱도 분할정복처럼 구현할 수 있다.

import sys
input= sys.stdin.readline

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

def mul(matrix1,matrix2):
    ans=[[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                ans[i][j] += matrix1[i][k]*matrix2[k][j]
            ans[i][j] %=1000
    return ans

def DoC(M,Matrix):
    if M==1:
        return Matrix
    elif M==2:
        return mul(Matrix,Matrix)
    else:
        tmp=DoC(M//2,Matrix)
        #홀수이면
        if M%2:
            return mul(mul(tmp,tmp),Matrix)
        else:
            return mul(tmp,tmp)

res = DoC(M,board)
for row in res:
    for cell in row:
        print(cell%1000,end=" ")
    print()