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

🤔 생각

• 행렬 제대로 인덱싱하는게 오래걸린 문제였다

• 처음엔 numpy의 np.dot (행렬곱 메소드) 연속 호출로 해결하면 되겠다고 생각했는데

• 백준은 numpy가 안 된다 프로그래머스는 왜 되는걸까

• 뇌에 힘 줘서 행렬곱 메소드 하나 짰는데, 시간초과에 봉착했고

• 분할정복이라는 새로운 개념을 알게되었다.

  지수가 큰 거듭제곱은 꼭 분할정복으로 해결하자.

📌 내 풀이

초안

결과는 잘 가져오는데 모듈 임포트 에러난다. 당연한거였다...
분할정복도 적용하지 않았던 코드라 넘파이가 된다 해도 시간초과 떴을거다

import numpy as np
import sys
input = sys.stdin.readline
#print = sys.stdout.write

n,b = map(int, input().split())
frame = [list(map(int, input().split())) for _ in range(n)]
frame = np.array(frame).reshape(n,n)
naive = frame.copy()

for _ in range(b-1):
    frame = np.dot(frame, naive)
    
frame = frame % 1000
for i in frame:
    print(*i)

최종

import sys
input = sys.stdin.readline
#print = sys.stdout.write

def matrix(n, frame1, frame2):
    answer = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                answer[i][j] += frame1[i][k]*frame2[k][j]
            answer[i][j] %= 1000
    return answer

n,b = map(int, input().split())
naive = [list(map(int, input().split())) for _ in range(n)]
frame = naive.copy()
binary = str(bin(b))

if b == 1:
    for f in frame:
        print(*list(map(lambda x: x%1000, f)))
else:
    for b in binary[3:]:
        frame = matrix(n, frame, frame)
        if b == "1": frame = matrix(n, frame, naive)

    for f in frame:
        print(*f)

✔ 배운 점

• 분할정복 알고리즘
• 행렬곱 연산 복습
• numpy는 표준 라이브러리가 아니다...