[백준 10830] 행렬 제곱 (python)

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

10830번: 행렬 제곱

행렬 제곱 문제

행렬의 곱을 연속해서 반복해서 결과를 출력하는 문제

분할정복을 이용하면 어렵지 않게 구현 할 수 있다.

 

📌문제 접근 포인트

1. 행렬의 제곱을 구하기 위해선 먼저 행렬의 곱셈 연산을 해줘야 한다. 행렬의 곱을 먼저 만들어주자.
2. 이제 행렬의 곱을 구했으니, 제곱은 이 곱을 반복하는 연산이고, 빠르게 곱을 하기 위해서 분할 정복 개념을 사용해서 제곱을 구성해주자.
3. 문제 요구조건대로 1000으로 나눈 나머지를 구해서 출력해주면 된다.

⚙ 내가 푼 정답코드

def multi(a,b):
    X = [[0]*N for _ in range(N)]
    for i in range(N): # 행렬
        for j in range(N):
            for k in range(N):
                X[i][j] += a[i][k]*b[k][j] % 1000 #곱셈 연산
    return X

def square(x,n): #분할 정복을 이용해 요구 사항만큼 제곱하기
    if n == 1:
        return x
    temp = square(x,n//2)
    if n % 2 == 0 :
        return multi(temp,temp)
    else : 
        return multi(multi(temp,temp),x)

import sys
N, B = map(int,sys.stdin.readline().split())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
result = square(A,B)
for i in range(N): #요구조건 대로 1000으로 나눠주자
    for j in range(N):
        result[i][j] = result[i][j] %1000

for k in result:
    print(*k)