#370 백준 파이썬 [10830] 행렬 제곱 - 분할 정복

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

 

SOLUTION

분할정복으로 풀 수 있는 문제다.

말그대로 말도 안되는 큰 연산을 요구하는 문제를 작은 단위로 쪼개서 계산한 다음, 다시 연산해주는 것이다.

 

분할정복!! 어렵지 않다.

A행렬을 N번곱할때 연산을 N-1번 수행해주는 것은 옳지 않다. (시간 복잡도)

N이 15인 수를 구한다면, A를 14번 곱해주는 대신에

(A**8) * (A**4) * (A**2) * (A**1) 이런식으로 제곱 가능한 숫자로 구성해준다면

3번, 2번, 1번, 0번 --> 총 6번, 그리고 각자 곱하는 3번을 포함해 9번만에 끝날 수 있다.

 

작은 숫자를 제곱하면 별 차이가 없겠지만 N이 문제와 같이 크다면

99,999,999,999번의 연산을

360번정도의 연산으로 줄일 수 있다. (2진법으로 변환해보라!)

360번은 2진법으로 나타냈을 때 '1'인 자릿수들의 위치 + 곱해주는 횟수 이다.

파이썬으로는 다음과 같이 나타낼 수 있다.

PYTHON CODE

#행렬 곱셈 함수
def matrix_mul(a, b):
    result = [[0]* 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] * b[k][j]
    
    for i in range(N):
        for j in range(N):
            result[i][j] %= 1000
                
    return result
    
    
#2진법으로 변환하여 분할정복 실행
N, B = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]
B = bin(B)[2:] #2진법으로 변환

#단위 행렬
identity_matrix = [[1 if i == j else 0 for i in range(N)] for j in range(N)]

#2진법 자릿수 만큼 제곱 & 제곱한 행렬 끼리 곱해줌
result = identity_matrix[:]
for i in range(len(B)):
    if B[-i-1] == '1':
        temp = matrix[:]
        while i != 0:
            temp = matrix_mul(temp, temp)
            i -= 1
        result = matrix_mul(result, temp)

for row in result:
    print(*row)