[백준 파이썬] 10830 행렬 제곱

📌문제 출처

백준 단계별 문제풀이 - 분할정복
https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱

❓ 문제

 

❗ 풀이

• 분할 정복(재귀 함수) 사용

📗 풀이 코드

import sys
input = sys.stdin.readline
def mul_func(a1,a2): # 행렬 곱 연산 함수
    mul = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        a1_row = a1[i]
        for j in range(n):
            a2_col = [a2_row[j] for a2_row in a2]
            mul[i][j] = sum([num_a1*num_a2 for num_a1,num_a2 in zip(a1_row,a2_col)])%1000
    return mul

def dac(a,b): # 분할 정복 함수 input = 행렬, 연산횟수
    if b == 1:
        for i in range(n):
            for j in range(n):
                a[i][j] %= 1000
        return a
    if not b%2: # b가 짝수라면
        return dac(mul_func(a,a),b//2) # 제곱행렬끼리의 ㅠ//2번 연산을 추가 진행
    else : # b가 홀수라면
        return mul_func(dac(mul_func(a,a),b//2),a) # 짝수일때 연산 진행 후 마지막에 a 한번 더 곱하기

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

for row in dac(a,b):
    print(*row)

📗 코드 해설

• 행렬 곱 연산과 분할 정복 연산을 함수로 생성
• 제곱의 나머지는 나머지의 제곱의 나머지와 같음을 이용
• b가 짝수라면 제곱 행렬끼리의 연산을 기본 배열로 활용하여 횟수를 2로 나눈다.
• b가 홀수라면 횟수에서 1을 뺀 뒤 위를 반복하고 마지막에 기본 배열을 한번 더 곱해준다.