[분할정복] 백준 10830번 행렬 제곱 with Python3 ★★

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

10830번: 행렬 제곱

 

문제

 

내 풀이

n, b = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
print(matrix)
answer = []
for i in range(n):
    answer.append([1] * n)
print(answer)
sum = 0

for _ in range(b):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                sum = matrix[i][k] * matrix[j][k]
                answer[i][j] = answer[i][j] + sum

print(answer)

해설

우선 단순히 행렬 제곱만을 구현해보았다. 

 

하지만 분할 정복을 하는 방법을 구현하지 못해 답을 보았다.

 

 

정답 풀이

# 행렬 곱셉 함수
def multiply(n, matrix1, matrix2):
    result = [[0 for _ in range(n)] for _ in range(n)]  # n *n 의 행렬 제작

    for i in range(n):
        for j in range(n):
            for k in range(n):
                result[i][j] += matrix1[i][k] * matrix2[k][j]
            result[i][j] %= 1000  # 답에서 요구하듯 각 결과 값을 1000의 나머지로 바꿔준다.

    return result

# 2분할 함수


def divide(n, b, matrix):
    if b == 1:
        return matrix
    elif b == 2:
        return multiply(n, matrix, matrix)
    else:
        tmp = divide(n, b//2, matrix)
        if b % 2 == 0:  # 짝수라면
            return multiply(n, tmp, tmp)
        else:  # 홀수라면
            return multiply(n, multiply(n, tmp, tmp), matrix)
            # 홀수 일 경우 A^5 -> A^2 * A^2 * A 한번을 더 해줘야한다.


# 입력
n, b = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

result = divide(n, b, a)

for row in result:
    for num in row:
        print(num % 1000, end=' ')
    print()

출처:https://hooongs.tistory.com/114

 

해석

홀수 일 경우 특이한 형태가 나오는 것 이외에는 대체적으로 이해가 된것 같다.