10830. 행렬 제곱

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	47878	17399	13739	34.781%

문제

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

풀이

def dq(b):  
    if b == 1:  
        return A  
    a = dq(b//2)  
    r = matrix_mul(a,a)  
    if b % 2 == 0:  
        return r  
    else:  
        return matrix_mul(r, A)  
  
def matrix_mul(a, c):  
    result = [[0 for _ in range(N)] for _ in range(N)]  
  
    for i in range(N):  
        for j in range(N):  
            for k in range(N):  
                result[i][j] += (a[i][k] * c[k][j]) %1000  
            result[i][j] %= 1000  
    return result  
  
N, B = map(int,input().split())  
A = [list(map(int, input().split())) for _ in range(N)]  
D = dq(B)  
  
for i in A:  
    for j in range(N):  
        i[j] = i[j]%1000  
  
for i in range(N):  
    print(*D[i])

• 1629. 곱셈 문제랑 유사한데, 재귀 구조를 짜는게 훨씬 힘들었음.
• 분할 하는건 괜찮은데 분할하고 어떻게 시간복잡도를 줄일 것인지도 어려웠고
• 간접재귀다 보니까 구조가 더 헷갈렸던 것 같음

Computer #PS