문제링크:https://www.acmicpc.net/problem/10830
10830번: 행렬 제곱
크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
다루는 주제: 분할정복
import sys
N, B = map(int, sys.stdin.readline().split()) # N*N행렬 입력 , B만큼 제곱
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 행렬 받기
# NxN 행렬 곱셈 함수
def multiplication(n, a, b):
result = [[0] * n for _ in range(n)]
for row in range(n):
for column in range(n):
for i in range(n):
result[row][column] += a[row][i] * b[i][column]
result[row][column] %= 1000
return result
def cal(n, b, a):
# 1 제곱
if b == 1:
return a
# 2 제곱
elif b == 2:
return multiplication(n, a, a)
else:
temp = cal(n, b // 2, a)
# b가 짝수일 경우
if b % 2 == 0:
return multiplication(n, temp, temp)
# b가 홀수일 경우
else:
return multiplication(n, multiplication(n, temp, temp), a)
result = cal(N, B, A)
for c in result:
for num in c:
print(num % 1000, end=' ')
print()
'Algorithm > 백준(파이썬)' 카테고리의 다른 글
백준 2805 파이썬(Python) 문제풀이 나무자르기 (0) | 2023.04.19 |
---|---|
백준 2493 파이썬(Python) 문제풀이 탑 (0) | 2023.04.19 |
백준 6549 파이썬(Python) 문제풀이 히스토그램에서 가장 큰 직사각형 (0) | 2023.04.17 |
백준 1629 파이썬(Python) 문제풀이 곱셈 (0) | 2023.04.16 |
백준 2630 파이썬(Python) 문제풀이 색종이 만들기 (0) | 2023.04.16 |