백준 GOLD 4 [10830번] 행렬 제곱 {언어 : Python}

문제 링크

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

정답 코드

import sys
input = sys.stdin.readline
n, b = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
optimization = dict()
# matrix의 원소가 1000이하이기 때문에 처음부터 걸러준다.
for i in range(n):
    for j in range(n):
        matrix[i][j] %= 1000
optimization[1] = matrix

# cal = calculation
def cal(leftM, rightM):
    newM = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                newM[i][j] += (leftM[i][k] * rightM[k][j]) % 1000
            newM[i][j] %= 1000
    return newM
# dac = divide and conquer
def dac(depth):
    if depth == 1:
        return matrix
    elif depth == 2:
        return cal(matrix, matrix)
    else:
        if optimization.get(depth, 0) == 0:
            if depth % 2:
                optimization[depth] = cal(dac(depth//2+1), dac(depth//2))
            else:
                optimization[depth] = cal(dac(depth//2), dac(depth//2))
        return optimization[depth]
answer = dac(b)
for a in answer:
    print(*a)

풀이 방법

1. 분할정복으로 풀었다.
2. 만약 10제곱이라면
   1. 2등분해서 5 5로 나누고
   2. 5를 2 3으로 나누고
   3. 2는 1 1
   4. 3은 다시 2 1
   5. 2는 1 1
   6. 이렇게 나눠서 가장 깊숙한 지점부터 계산해서 올라 온다.
3. 만약 n제곱이 존재하면 계산할 필요가 없이 dictionary에서 찾을 수 있도록 최적화 했다.
   1. 이렇게 하지 않았다면 시간초과가 걸렸을 것이다.
4. 맨 처음에 1000으로 나누어 떨어뜨리는 이유
   1. 주어진 행렬의 원소가 1 <= elem <= 1000 이고 결과값은 원소 모두가 1000으로 나누어 떨어진 값이어야 하기 때문이다.
   2. 이렇게 안 하면 거듭제곱이 1이고 원소가 다 1000일 경우 틀린 값이 나오게 된다.
5. 계산이 완료되면 answer에 넣고 출력하면 끝!

느낀점

• 문제를 잘 읽어도 이런 문제는 실수를 유도하는 것 같다.
• b의 값이 100,000,000,000이었기 때문에 분할 정복을 유추할 수 있었다.
• 이미 계산한 과정은 생략하고 바로 값을 찾을 수 있도록 딕셔너리에 넣는 방법을 배웠다.