[분할정복/DQ] 백준 10830 행렬 제곱 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

10830번: 행렬 제곱

 

 

 

2. 문제 풀이

 행렬 A의 B 거듭제곱을 구하는 문제입니다.

 

 행렬의 곱셈은 위와 같이 행과 열의 곱으로 이루어집니다. 반복문으로 구현하려면 무려 3중 for문을 써야 합니다. (O(n^3)) 따라서 계속 A를 곱하는 방법으로는 당연히 시간초과가 납니다.

 

2022.05.08 - [Algorithm] - [분할정복/재귀] 백준 1629 곱셉 - 파이썬(Python)

 그 대신 A^B제곱을 A가 될 때까지 둘로 나눈다음, 다시 곱해주면 효율적으로 구할 수 있습니다. 분할정복 방식으로, 위 문제를 먼저 풀고 이 문제를 푸시는 걸 추천드립니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
N, B = map(int, input().split())
matrix = []
for _ in range(N):
    matrix.append(list(map(int, input().split())))

# 행렬 곱셈
def mul_matrix(mat1, mat2):
    res = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for z in range(N):
                # c11 = a11*b11 + a12*b21
                res[i][j] += mat1[i][z] * mat2[z][j] % 1000
    return res

 행렬의 곱셈을 구현합니다. 3중 for문을 이용하면 행렬곱을 구현할 수 있습니다.

 

 

# 분할정복
def power(a, b):
    if b == 1:  # b의 값이 1이 될 때까지 재귀
        return a
    else:
        tmp = power(a, b // 2)  # a^(b // 2)
        if b % 2 == 0:
            return mul_matrix(tmp, tmp)  # b가 짝수인 경우
        else:
            return mul_matrix(mul_matrix(tmp, tmp), a)  # b가 홀수인 경우
result = power(matrix, B)

# 출력
for row in result:
    for col in row:
        print(col % 1000, end=" ")
    print()

 1629번의 곱셈 문제와 마찬가지로 분할정복을 이용합니다. 단순히 달라진 점은 *대신 mul_matrix() 행렬곱이 들어간 것 뿐입니다.

 이후 원소별로 1000으로 나눈 나머지를 출력합니다.