[백준] 10830번: 행렬 제곱 - Python

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

10830번: 행렬 제곱

분할 정복 문제이다 

구현은 2가지 함수로 크게 나누었다. 

1. def multiply() : 행렬과 행렬을 곱셈한후 return 해주는 함수 

특별한것 없이 행렬 계산을 for 문으로 구현했다.

2. def solve() : 분할정복으로 연산하는 함수 

지수 B가 홀수 일 때와 짝수일때를 나눠서 연산했다 지수이니까 ..!

예를들어서 지수가 (=B 값이) 5인 경우 도식화 해보면 다음과 같다 

5를 5//2 로 나눈 값을 square_array에 저장한다 

5는 홀수이므로 square_array를 제곱한 값에 array를 한번 더 곱해주어야 한다 

multiply(multiply(square_array, square_array), array)

 

전체 코드 

N, B = map(int ,input().split()) # 행렬 A의 B제곱 구하기 
array = []
for i in range(N):

    array.append(list(map(int, input().split())))

# 행렬 곱셈
def multiply(array1, array2):
    result = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            temp = 0
            for k in range(N):
                temp += array1[i][k] * array2[k][j]
            result[i][j] = temp%1000
    return result 


#           5
#        /  |   \
#      /    |     \
#    2       2     1
#   / \    /  \
#  1   1   1   1


def solve(array, B):

    if B == 1:
        for i in range(N):
            for j in range(N):
                array[i][j] %= 1000
        return array
    square_array = solve(array, B//2)
    if B%2 == 0: # 짝수
        return multiply(square_array, square_array)
    else: # 홀수
        return multiply(multiply(square_array, square_array), array)

result = solve(array, B)
# 출력 
for i in range(N):
    print(*result[i])