반응형
https://www.acmicpc.net/problem/10830
행렬 제곱 문제
행렬의 곱을 연속해서 반복해서 결과를 출력하는 문제
분할정복을 이용하면 어렵지 않게 구현 할 수 있다.
📌문제 접근 포인트
1. 행렬의 제곱을 구하기 위해선 먼저 행렬의 곱셈 연산을 해줘야 한다. 행렬의 곱을 먼저 만들어주자.
2. 이제 행렬의 곱을 구했으니, 제곱은 이 곱을 반복하는 연산이고, 빠르게 곱을 하기 위해서 분할 정복 개념을 사용해서 제곱을 구성해주자.
3. 문제 요구조건대로 1000으로 나눈 나머지를 구해서 출력해주면 된다.
⚙ 내가 푼 정답코드
def multi(a,b):
X = [[0]*N for _ in range(N)]
for i in range(N): # 행렬
for j in range(N):
for k in range(N):
X[i][j] += a[i][k]*b[k][j] % 1000 #곱셈 연산
return X
def square(x,n): #분할 정복을 이용해 요구 사항만큼 제곱하기
if n == 1:
return x
temp = square(x,n//2)
if n % 2 == 0 :
return multi(temp,temp)
else :
return multi(multi(temp,temp),x)
import sys
N, B = map(int,sys.stdin.readline().split())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
result = square(A,B)
for i in range(N): #요구조건 대로 1000으로 나눠주자
for j in range(N):
result[i][j] = result[i][j] %1000
for k in result:
print(*k)
반응형
'알고리즘 풀이 > 백준' 카테고리의 다른 글
[백준 25974] 거듭제곱의 합1 (python) (0) | 2023.04.09 |
---|---|
[백준 1492] 합 (python) (0) | 2023.04.09 |
[백준 2740] 행렬 곱셈 (python) (0) | 2023.04.09 |
[백준 15965] K번째 소수 (python) (0) | 2023.04.08 |
[백준 9735] 삼차 방정식 풀기 (python) (0) | 2023.04.08 |
댓글