[백준 BOJ_10830] 행렬 제곱 Python 풀이

출처: 백준 온라인 저지

문제

풀이

우선 아래의 행렬의 곱셈을 구하는 선행문제에서 multiply함수를 가져옵니다.

[백준 BOJ_2740] 행렬 곱셈 Python 풀이

거듭제곱을 연속하였을 때 수가 커지는 것을 미연에 방지하기위해, 곱해줄 때마다 1000으로 나눈 값으로 저장해줍니다.

그 다음은 거듭제곱을 분할정복으로 구하는 함수는 이미 아래의 문제에서 풀었습니다.

[백준 BOJ_1629] 곱셈 Python 풀이

이 함수를 행렬의 곱셈에 맞게 바꿔줍니다.

제곱이 0일 경우(기저사례)를 위해 곱해줄 항등행렬을 만들어주는 identity 함수도 만들어주었습니다.

코드

def multiply(a, b):
    c = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                c[i][j] = (c[i][j]+a[i][k]*b[k][j])%1000
    return c
def identity(n):
    c = [[0] * n for _ in range(n)]
    for i in range(n):
        c[i][i] = 1
    return c
def power(a, exp):
    if exp == 0:
        return identity(N)
    half = power(a, exp // 2)
    if exp % 2:
        return multiply(multiply(half, half), a)
    return multiply(half, half)
N, B = map(int, input().split())
A = [ list(map(int, input().split())) for _ in range(N)]
C = power(A, B)
for c in C:
    print(*c, sep=" ")