[G4] 백준 10830 - 행렬 제곱 (Python3)

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

---

💡 해결방법

분할 정복을 활용한 제곱으로 해결했다.

👀 풀이

x^n = x^{n/2} * x^{n/2} 을 이용한 풀이 방법이다.

1629 곱셈에서 먼저 적용해볼 수 있다.

---

🧾코드

# 10830

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

I = [[0]*N for _ in range(N)]
for i in range(N):
    I[i][i] = 1

def square(mat, n):
    if n == 1:
        return matrix_multiplication(mat, I)
    elif n%2 == 0:
        return square(matrix_multiplication(mat, mat), n//2)
    else:
        return matrix_multiplication(mat, square(matrix_multiplication(mat, mat), (n-1)//2))

def matrix_multiplication(A, B, mod=1000):
    ln = len(A)
    C = [[0]*ln for _ in range(ln)]
    for i in range(ln):
        for j in range(ln):
            for k in range(ln):
                C[i][j] += (A[i][k] * B[k][j]) % mod
            C[i][j] %= mod
    return C
    
result = square(matrix, b)
for elm in result:
    print(*elm)

---

🚨 틀렸던 이유

문제에서 주어진대로 입력되는 행렬 원소의 최대값이 1,000 이다. 그러므로 B가 1인 경우를 대비해서 단위 행렬(I) 를 만들어서 모듈러 연산(나머지 연산)을 행렬에 해주어야한다. 이것을 나중에 아는 바람에 한참 헤맸다..