[BOJ] 10830 행렬제곱 파이썬

1. 문제

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

2. 입력

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

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

3. 출력

첫째 줄부터 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나누기 처리를 안해주었기 때문!

 

아래는 정답 소스

      

      

      

    
    

      <python />
    
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)))

한번 누르면 2시간동안 보이지 않아요 ㅎㅎ 이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.

원치 않을 경우 를 눌러주세요