[PY] 10830 : 행렬 제곱

 

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

처음 문제 제목만 보고, 아 이건 상용화 된 알고리즘을 써야겠다라고 생각하고 덮어두고 있었다.
근데 실 적용을 하려고 보니 뭔가뭔가 삐그덕 댈 것 같은 조짐이 보여서 이게 아닌가 싶었다.

좀 치는 사람에게 물어보니 그냥 직접 해결했다고 했다. 엥 이걸 그냥 직접 해결 할 수 있다고?

그래서 문제 하나를 보고 그냥 생각했다. 그냥 보고 있으니 기존에 풀었던 문제와 비슷한 점이 있었다.

2025.03.22 - [문제풀이] - [PY] 1629 : 곱셈

[PY] 1629 : 곱셈

연산을 줄이는데에 핀트가 있으면 곱셈의 코드 형식이 분할 정복의 대표적 예제가 아닐까 생각한다.
어쨌든, 곱셈에서 구현된 코드를 가져와서 행렬에 적합한 형태로만 다시 고려한다면 되는 문제였다.

끝 판에 이런 테스트 케이스를 보았다.

2 1
1000 1000
1000 10000

출력은
0 0
0 0

왜냐하면, 나누기 1000 이후 나머지를 출력하는 루틴의 적용 여부를 봐야하기 때문이었다.
base case에서 무작정 기존 행렬만 반환하던 것을 허겁지겁 항등행렬 (= 행렬에서 이 행렬과 곱셈하면 1을 곱한 것과 동일하다)
과의 곱셈을 시도해서 기존의 % 1000 코드가 적용되도록 했다.

 

import sys



def multipleMatrix(matA, matB, size):
    matC = [[0 for col in range(size)] for row in range(size)]
    for i in range(size):
        for j in range(size):
            for k in range(size):
                tmpResult = (matA[i][k] % 1000) * (matB[k][j] % 1000)
                matC[i][j] += tmpResult
                matC[i][j] %= 1000

    return matC

def multipleAdmin(matrix, multiVal):
    if(multiVal == 1):
        return multipleMatrix(originMat, IdentityMat, matSize)
    
    value = multipleAdmin(matrix, multiVal // 2)

    if(multiVal % 2 == 0):
        return multipleMatrix(value, value, matSize)
    else:
        return multipleMatrix(multipleMatrix(value, value, matSize), originMat, matSize)

   
matSize, multipleCnt = list(map(int, sys.stdin.readline().strip().split()))
originMat = [list(map(int,input().strip().split())) for _ in range(matSize)]
IdentityMat = [[0 for col in range(matSize)] for row in range(matSize)]

for i in range(matSize):
    IdentityMat[i][i] = 1

resultMat = multipleAdmin(originMat, multipleCnt)



for i in range(matSize):
    for j in range(matSize):
        print(str(resultMat[i][j]) + " ", end="")
    print("")