[Python] 백준 10830번 행렬 제곱

문제

크기가 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제곱한 결과를 출력한다.

 

10830번: 행렬 제곱

---

접근 방법

B제곱의 범위 (1 ≤ B ≤ 100,000,000,000)인걸 보니 한번에 계산하지 않고 분할해서 재귀로 풀어야될거같다. 

1) 모듈러 연산은 분배법칙이 성립한다. 

    => (A * A) % C = A%C * A%C ※ 행렬의 각 항목에 대한 모듈러 연산이다.

2) 재귀함수 사용

 

import sys

n, b = map(int, input().split()) 
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
c = 1000

def matrixmult(A,B):
    n = len(A)
    C=[[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j]+=A[i][k]*B[k][j]
            C[i][j] = C[i][j] % c #곱하면서 바로바로 모듈러연산을 해준다. 
    return C

def g(a: list ,b: int):
    temp = [[0]*n for _ in range(n)]
    if b == 1:
        for i in range(n):
            for j in range(n):
                a[i][j] %= c
        return a
    
    else:
        matrix =g(a, b//2)
        if b % 2 == 0:
            temp = matrixmult(matrix, matrix)
            return temp 
        else:
            temp = matrixmult(matrixmult(matrix, matrix), a)
            return temp

for ans in g(arr, b):
   print(*ans)

 

# 똑같은 실수는 하지말자

# 재귀함수내 종료조건
def g(a: list ,b: int):
    temp = [[0]*n for _ in range(n)]
    if b == 1:
        for i in range(n):
            for j in range(n):
                a[i][j] %= c
        return a
# 재귀 종료 조건에 모듈러 연산을 안하면, A^1 계산시 모듈러 연산 적용이 안되는 반례 존재