[백준] 10830 : 행렬 제곱

문제

참고한 풀이

https://velog.io/@ledcost/백준-10830-파이썬-행렬-제곱-골드4-분할-정복

이 분의 코드를 참고했다.
행렬의 거듭 제곱 문제이므로, 알고리즘으로 거듭제곱을 구현하기 위해서는 자연수의 거듭 제곱 풀이인 https://www.acmicpc.net/problem/1629 문제 부분을 가지고 만들어야 했다.

그리고,

행렬 제곱은 기본적으로 행렬 곱셈을 코드로 구현해낼 수 있어야 하는데, 그 부분부터 공부했어야 했다.

특히, NxM, MxK 행렬을 곱하면 NxK 행렬이 된다는 부분이 중요하다.

https://velog.io/@ledcost/백준-2740-파이썬-행렬-곱셈-브론즈1-선형대수

행렬 곱셈 (백준 2740번)

import sys
n, m = map(int, sys.stdin.readline().split()) # n개의 줄에 m개씩 원소
a = [list(map(int, input().split())) for _ in range(n)] # 리스트 안에 리스트를 여러번 인풋 받음 (2차원 배열)

m, k = map(int, sys.stdin.readline().split())
b = [list(map(int, input().split())) for _ in range(m)]

# N(행)*M(열), M(행)*K(열) 행렬을 곱하면 N(행)*K(열) 행렬이 됨!!!
# N과 K에 대해 이중 for문을 돌면서, 벡터의 크기 M만큼 for 돌면서 
# 행벡터와 열벡터의 각 요소 곱의 더하기 값을 구해주고 결과 행렬에(2차원 리스트) 넣어주면 된다.

axb = [[0]*k for _ in range(n)]
for row in range(n):
    for col in range(k):
        e = 0
        for i in range(m):
            e += a[row][i] * b[i][col]
        axb[row][col] = e
    
for r in axb:
    print(*r)

풀이

# 자연수의 거듭제곱 풀이와 행렬의 곱셈 풀이 합쳐놓은 문제
import sys
input = sys.stdin.readline

N, B = map(int, input().split())
A =  [[*map(int, input().split())] for _ in range(N)]

def mul(U, V): # 두 행렬의 곱셈 구하는 함수
    n = len(U)
    Z = [[0]*n for _ in range(n)]
    
    for row in range(n):
        for col in range(n):
            e = 0
            for i in range(n):
                e += U[row][i] * V[i][col]
            Z[row][col] = e % 1000
    
    return Z

def square(A, B): # A 행렬을 B 제곱하는 함수
    if B == 1:
        for x in range(len(A)):
            for y in range(len(A)):
                A[x][y] %= 1000
        return A
    
    tmp = square(A, B//2)
    
    if B % 2 : # 제곱하는 횟수가 홀수일 때
        return mul(mul(tmp, tmp), A)
    else:
        return mul(tmp, tmp) 
    
result = square(A, B)
for r in result:
    print(*r) 
        

cf. 자연수의 거듭제곱

import sys
 
a, b, c = map(int, sys.stdin.readline().split())

#  지수를 매번 2로 나눠 더 작은 문제로 만들어 해결하는 분할정복 방식

def power(a, b):
    if b == 0:
        return 1
    
    x = power(a, b//2)
    
    if b % 2 == 0:
        return x * x
    else:
        return x * x * a

print(power(a, b)%c)