[백준 10830번][Python] - 행렬 제곱

https://www.acmicpc.net/problem/10830

 

 

 

 

 

# 풀이과정

주어지는 제곱수의 범위가 최대 10억이기에, 이걸 전부 수행하면 시간초과가 발생한다.

따라서, 분할정복을 이용하여 지수를 나누어서 계산해줘야함

 

이를 정리하면 다음과 같다.

1. expon이 1이면 현재 그래프 g를 그대로 반환
2. expon이 2면 g와 g를 한번 행렬곱한 결과를 반환
3. expon이 1,2가 아니면 아니라면?
4. expon을 절반의 정수값으로 줄여서 main함수를 호출해서 반환받은 값을 temp로 저장
5. expon이 짝수이면 temp와 temp를 행렬곱한 결과를 반환
6. expon이 홀수이면 temp와 temp를 행렬곱하고, 거기에 g를 행렬곱한 결과를 반환
7. main함수로부터 반환받은 그래프의 요소들을 1000으로 모듈러 연산 수행한 값을 출력

 

[분할정복 - 성공]

# ex_10830
# 분할정복
import sys
graph = []
N,B = map(int, sys.stdin.readline().split())
for _ in range(N):
    elements = list(map(int, sys.stdin.readline().split()))
    graph.append(elements)
new_graph = graph
expon = 1   # 지수

def getProd(g1,g2):
    result=[]
    for i in range(N):  # 행
        subr=[]
        for j in range(N):  # 열
            v = 0
            for k in range(N):
                v += g1[i][k]*g2[k][j]
            subr.append(v%1000)  # 각 행
        result.append(subr)
    return(result)


def sol(g,expon):
    if expon == 1:
        for i in range(N):
            return(g)
    elif expon == 2:
        return(getProd(g,g))
    else:
        temp = sol(g,expon//2)
        if expon%2 == 0:
            return(getProd(temp,temp))
        else:
            return(getProd(getProd(temp,temp),g))

result = sol(graph,B)
for l in result:
    for num in l:
        print(num%1000, end=' ')
    print()