[BOJ] 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제곱한 결과를 출력한다.

 

 

문제 자체가 간단해보인다.

일단 인터넷에 행렬곱셈코드를 가지고 복붙하여 b만큼 for문을 돌려서 제곱해준다.

=> 안좋은 느낌은 빗나가지 않는다! 당연히 시간초과가 난다.

 

제곱을 빨리계산하는 방법은? => 분할정복

2^8을 계산하려고 8번 곱하는게 아니라

2^4 * 2^4 등으로 바꾸어 생각할 수 있다는 뜻!

나름 더 빠르게 해보겠다고 메모이제이션썼으나, 메모리초과로 실패!

그래서 단순히 b를 홀/짝에 나누어 분기처리해주고 재귀로 분할정복 넣었더니 80%에서 오답!

마의 히든테케인

2 1

1000 1000

1000 1000 때문..

답은

0 0

0 0

틀린이유는 b=1일때 1000나누기 처리를 안해주었기 때문!

 

아래는 정답 소스

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, b = map(int, input().rstrip().split(" "))

matrix = []
for i in range(n):
    matrix.append(
        [*map(lambda x: x % 1000, map(int, input().rstrip().split(" ")))])


def productMatrix(arr1, arr2):
    answer = []
    for idx1 in range(len(arr1)):
        row = []
        for idx2 in range(len(arr2[0])):
            tmp = 0
            for idx3 in range(len(arr1[0])):
                tmp += arr1[idx1][idx3] % 1000 * arr2[idx3][idx2] % 1000
                tmp = tmp % 1000
            row.append(tmp)
        answer.append(row)
    return answer


def solve(tmp_b):
    global matrix
    if(tmp_b == 1):
        return matrix
    t = solve(int(tmp_b/2))
    t = productMatrix(t, t)
    if(tmp_b % 2 != 0):
        t = productMatrix(t, matrix)
    return t


for m in solve(b):
    print(" ".join(map(str, m)))