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

 

10830번: 행렬 제곱

 

문제

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

입력

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤  5, 1 ≤ B ≤ 100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

 

예제 입력 1  2 5 1 2 3 4	예제 출력 1  69 558 337 406
예제 입력 2  3 3 1 2 3 4 5 6 7 8 9	예제 출력 2  468 576 684 62 305 548 656 34 412
예제 입력 3  5 10 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1	예제 출력 3  512 0 0 0 512 512 0 0 0 512 512 0 0 0 512 512 0 0 0 512 512 0 0 0 512

 

풀이

 

분할 정복을 통해 행렬 제곱을 구하는 문제이다.

 

최대 100,000,000,000 제곱을 구해야 하므로, 일반적으로 곱해주면 당연히 시간초과가 뜰 것이다.

 

제곱수를 작게 쪼개어서 구해주도록 하자.

 

 

예를 들어 a^16을 구해보도록 하자.

 

a^16 = a^8 * a^8

a^8 = a^4 * a^4

a^4 = a^2 * a^2

a^2 = a * a

 

연산 횟수가 16번에서 확 줄어듦을 알 수 있다. 

 

 

다음 예로 a^10을 구해보자.

 

a^10 = a^5 * a^5

 

어, 지수가 홀수이기 때문에 2로 나누면 소수점이 된다.

 

때문에 지수가 홀수일 경우 맨 처음의 행렬 a를 곱해주는 처리를 해주도록 하자. 즉,

 

a^10 = a^5 * a^5

a^5 = a^2 * a^2 * a

a^2 = a * a

 

위와 같은 순서로 처리가 된다.

 

import sys
input = sys.stdin.readline

n, B = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]

def dac(s,b):
    if b == 1:
        return s
        # base code
    
    a = dac(s,b//2)
    
    cal = []
    for i in range(n):
        temp = []
        for j in range(n):
            num = 0
            for k in range(n):
                num += a[i][k] * a[k][j]
            temp.append(num%1000)
        cal.append(temp)
    # 위 연산을 함수화해서 아래의 코드 길이를 줄일 수도 있다.
    result = []
    if b % 2:
    	
        for i in range(n):
            temp = []
            for j in range(n):
                num = 0
                for k in range(n):
                    num += cal[i][k] * A[k][j]
                temp.append(num%1000)
            result.append(temp)
    else:
        result = cal
        
    return result
for i in dac(A,B):
    for j in i:
        print(j%1000, end =" ")
        # 위 처리를 해주지 않을 경우 
        # 2 1
        # 1000 1000
        # 1000 1000
        # 같은 입력에 0이 아닌 1000을 출력하여 틀리게 된다.
    print()