행렬 제곱 ( 10830번 )

💻 백준 10830번: 행렬 제곱

📌 문제 설명

정수 N(2 ≤ N ≤ 5), B(1 ≤ B ≤ 100,000,000)이 주어졌을 때,
N × N 크기의 행렬 A를 B번 곱한 결과를 구하라.
(결과는 각 원소를 1000으로 나눈 나머지로 출력)

10830번: 행렬 제곱

 

 

🧠 핵심 아이디어

• 행렬의 거듭제곱은 **분할 정복(Divide and Conquer)**을 이용해 효율적으로 계산 가능
• 매번 곱할 때마다 모듈로 1000 연산을 적용하여 숫자 범위를 제한함
• b가 매우 크기 때문에 O(n × b)로는 시간 초과 발생 → O(log b) 접근 필요

 

✨ 나의 풀이

import sys

def _make_list(n):
    answer = []
    for _ in range(n):
        now_list = list(map(int, sys.stdin.readline().rstrip().split()))
        for idx in range(len(now_list)):
            now_list[idx] %= 1000
        answer.append(now_list)
    return answer


def _cr_mt(A, B): ## 행렬 계
    answer = [[0]*len(B[0]) for _ in range(len(A))]
    for i in range(len(A)):
        for j in range(len(B[0])):
            for u in range(len(B)):
                answer[i][j] += (A[i][u] * B[u][j])
            answer[i][j] %= 1000
    return answer


def _main(b, n_list): ## 분할 정복
    if b == 1:
        return n_list
    elif b % 2 == 0:
        half = _main(b//2, n_list)
        return _cr_mt(half, half)
    elif b % 2 != 0:
        return _cr_mt(n_list, _main(b-1, n_list))


n, b = map(int, sys.stdin.readline().rstrip().split())
n_list = _make_list(n)
result_list = _main(b, n_list)
for i in result_list:
    print(' '.join(list(map(str, i))))

 

 

⏱ 시간 복잡도 분석

 

def _main(b, n_list) : b를 분할 정복 ( 로그 시간 복잡도 )
    _cr_mt(half, half) : 행렬 계산 함수 ( 삼차형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 삼차형 로그 시간 복잡도 ( O(n**3 log n) )