백준_10830_행렬 제곱

문제

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

10830번: 행렬 제곱

풀이

1) 분할 정복을 이용한 거듭제곱

number을 n번 곱한다고 하면, 아래처럼 적을 수 있다. 이를 행렬에도 적용하면, 문제를 해결할 수 있다.

def power(number, n) : 
    if n==0 : return 1
    elif n이 짝수 : return power(number², n//2)
    elif n이 홀수 : return number*power(number², n//2)

문제에서는 n의 최대값을 100000000000으로 두고 있다. n을 최대값으로 하더라도, 37번에서 탐색이 끝난다.

2) 행렬곱

https://ko.wikipedia.org/wiki/%ED%96%89%EB%A0%AC_%EA%B3%B1%EC%85%88

3) 1000으로 나눈 나머지 

1000으로 나누어진 행렬을 반환해야 하므로, 아래와 같은 예제를 고려해야 한다.

ex) 행렬A를 1번 제곱하면 행렬B를 반환해야 한다.

코드

# 행렬의 제곱 처리하기
def power(arr, n):
    if n<=1 : return remainder(arr)
    if n%2==0 : 
        square = product(arr, arr)
        return power(square, n//2)
    else : 
        square = product(arr, arr)
        temp = power(square, n//2)
        return product(arr, temp)

# 행렬 * 행렬
def product(a, b) :
    answer = [[0 for j in range(N)] for i in range(N)]
    for i in range(N) :
        for j in range(N) : 
            for k in range(N) : 
                answer[i][j] += a[i][k]*b[k][j]
    
    return remainder(answer)

# 1000으로 나눈 나머지 
def remainder(a) : 
    for i in range(N) : 
        for j in range(N) : 
            a[i][j]%=1000
    return a
            
N, B = map(int, input().split())
arr = [list(map(int, input().split())) for i in range(N)]
ans = power(arr, B)

for i in range(N) : 
    print(" ".join(list(map(str, ans[i]))))