문제:
크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.
입력:
첫째 줄에 행렬의 크기 N과 B가 주어진다. (2<=N<=5, 1<=B<=100,000,000,000)
둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.
출력:
첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.
풀이방법:
B의 최대 크기가 100,000,000,000인 만큼 효율적인 계산 방법이 필요한 문제다. 따라서 다음과 같은 규칙에 의해서 계산을 한다.
A^N일 때,
if N이 짝수라면, (A^2)^(N/2)로 수정한다.
if N이 홀수라면, (A^(N-1))*A로 수정하고, A는 answer에 곱한다.
N이 1이 될 때까지 위를 반복하고, 1이면 그 때의 A를 answer에 곱한다.
위와 같이 계산을 한다면 지수가 log2단위로 줄어들기 때문에 최대 100,000,000,000번 연산이 최대 36번으로 줄어들게 될 것이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
n,b = map(int,input().split())
def matmul(A,B):
result = [[0]*len(A) for _ in range(len(B))]
for i in range(len(A)):
for j in range(len(B)):
for k in range(len(A[0])):
result[i][j] += A[i][k]*B[k][j]
result[i][j] %= 1000
return result
matrix = []
for _ in range(n):
matrix.append(list(map(int,input().split())))
answer = [[1 if i==j else 0 for i in range(n)] for j in range(n)]
while b !=1:
temp = matrix[:]
if b%2:
answer = matmul(answer,temp)
b-=1
else:
matrix = matmul(temp,temp)
b//=2
answer = matmul(answer,matrix)
for ans in answer:
print(*ans)
|
cs |
문제링크:
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]5052. 전화번호 목록 (0) | 2020.06.23 |
|---|---|
| [BOJ]12865. 평범한 배낭 (0) | 2020.06.18 |
| [BOJ]1837. 암호제작 (0) | 2020.06.11 |
| [BOJ]9506. 약수들의 합 (0) | 2020.06.09 |
| [Programmers]2018 Kakao[1차]추석 트래픽 (0) | 2020.05.26 |