알고리즘 스터디
[백준] 10830 : 행렬 제곱 - Python(파이썬)
히치키치
2021. 4. 6. 16:30
문제
10830번: 행렬 제곱
크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
빠른 거듭제곱 계산
풀이
- 분할 정복 & 재귀
- 빠른 거듭제곱 계산
- 거듭제곱 나누기 -> 행렬 계산 : 재귀적으로 구현
코드
#문제: https://www.acmicpc.net/problem/10830
def multi_mat(n,m1,m2):
result=[[0 for _ in range(n)] for _ in range(n)] #계산 결과 담는 행렬
for i in range(n):
for j in range(n):
for k in range(n):
result[i][j]+=m1[i][k]*m2[k][j] #행렬 계산 값을 결과 담는 행렬에 넣어줌
result[i][j]%=1000 #1000으로 나눈 나머지
return result
def dev(n,x,mat):
if x==1: #종료 : x // 2 = n = 0
return mat
else:
tmp=dev(n,x//2,mat)
if x%2==0: #짝수 제곱
return multi_mat(n,tmp,tmp)
else: #홀수 제곱
return multi_mat(n,multi_mat(n,tmp,tmp),mat)
n,x=map(int, input().split())
a=[list(map(int,input().split())) for _ in range(n)]
result=dev(n,x,a)
for i in result:
for j in i:
print(j%1000,end=' ') #종료 시 행렬이 그대로 반환 됨으로 %1000연산 필요함
print()