[백준] 10830(파이썬) - 행렬 제곱

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

10830번: 행렬 제곱

• 이 문제를 읽으면 먼저 어마어마한 입력값의 범위를 확인하고 시간 초과를 해결해야겠다고 생각이 들것이다.
• 그럼 어떻게 생각을 해야할까 를 고민하던 도중 시간 복잡도 O(N)을 절반씩 계산하면 O(logN) 이 될 거라고 생각했고 예를 들어 10번을 곱해야 한다면 5번 5번 곱한 값을 더해주면 되고 5번이면 2번 3번으로 나눌 수 있고 이렇게 아토믹하게 쪼개서 생각을 했다. (이 방법을 분할 정복 알고리즘이라고 부른다.)
• 그래서 dfs방식 처럼 재귀를 이용해서 계산했고, 최대한으로 쪼개서 제곱으로 만들었을 때와, 제곱이 아니라 원래 주어진 행렬을 곱해주는 때를 구분해서 구현하였다.
• b가 1일때는 그냥 현재의 행렬 원소를 각각 1000으로 나눠준 값을 넣어주면 된다.

import sys
input = sys.stdin.readline

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

def dfs(List,b):
    temp = [[0]*n for _ in range(n)]
    if b == 1:
        for i in range(n):
            for j in range(n):
                List[i][j] %= 1000
        return List
    elif b % 2 == 1:
        divide_matrix = dfs(List,b-1)
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    temp[i][j] += divide_matrix[i][k] * List[k][j]
                temp[i][j] %= 1000
        return temp
    elif b % 2 == 0:
        divide_matrix = dfs(List, b // 2)
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    temp[i][j] += divide_matrix[i][k] * divide_matrix[k][j]
                temp[i][j] %= 1000
        return temp

ans = dfs(data,b)

for i in ans:
    for j in i :
        print(j,end=" ")
    print()