백준 10830 행렬 제곱 (파이썬)
접근방식
구글링을 해보니 다양한 방법으로 풀이 할 수 있었지만 나는 백준 1629 곱셈 문제에서 사용한 알고리즘을 2차원 배열로 확장하는 방식으로 풀었다.
1629 곱셈 문제 풀이 바로 가기- 만약 b가 4일 경우(짝수), AAAA = (AA)(AA)= (AA)^2 = (A^2)^2 의 형태가 된다. A^(b//2)와 A^(b//2)를 곱하면 된다.
- 그러나 b가 5일 경우(홀수), AAAAA = (AA)(AA)A = ((AA)^2)A = ((A^2)^2)A 의 형태가 되고 뒤에 A를 한번 더 곱해주어야한다!
- 행렬을 곱할 시 % 1000을 해주었는데 마지막 출력시에도 % 1000을 하지 않을 시 b = 1이고 A가 1000으로 이뤄져있을 경우 문제가 발생한다고 한다.
파이썬 코드
import sys
n, b = map(int, sys.stdin.readline().split())
A = []
for _ in range(n):
A.append(list(map(int, sys.stdin.readline().split())))
# 행렬 곱하기(A*A) 알고리즘
def mul(n,a,b):
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] += a[i][k] * b[k][j]
result[i][j] %= 1000
return result
# 1629 곱셈 문제와 같은 형식
def cal(n,b,A):
if b == 1:
return A
# 단순 2제곱일 경우
elif b == 2:
return mul(n,A,A)
else:
temp = cal(n, b // 2, A)
# b가 짝수일 경우 제곱수를 계속 곱하면 된다.
# AAAA = ((A^2)^2)
if b % 2 == 0:
return mul(n,temp,temp)
# b가 홀수일 경우 마지막에 A를 곱해줘야한다.
# AAAAA = ((A^2)^2)*A
else:
return mul(n,mul(n,temp,temp),A)
result = cal(n,b,A)
for row in result:
for num in row:
print(num % 1000,end= ' ')
print()
