[백준알고리즘] 10830번: 행렬 제곱 -Python

[백준알고리즘] 10830번: 행렬 제곱 -Python

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

10830번: 행렬 제곱

빠른 모듈로 거듭제곱을 개념을 이용해 행렬 곱셈을 수행했다.

분할 정복의 개념을 사용했고 아래와 같은 방식에 각 원소마다 모듈로를 해주는 것으로 수행했다.

 

A^11 = A^10 * A^10 * A^1

A^8 = A^4 * A^4

 

코드 내용은 거의 같으나 @iknoom1107 님의 코드를 보니 for문으로 작성했던 부분을 sum()을 이용해 원소의 값을 구해주는 부분이나 마지막 출력 시에도 ' '.join(list(map(str, a)))으로 한 줄씩 출력해줬던 부분을 *a로 해주는 방법이 더 코드가 깔끔해 보이기 때문에 참조해서 추가해주었다.

def solve(b):
    rtn = [[0] * n for _ in range(n)]
    if b == 1:
        for i in range(n):
            for j in range(n):
                rtn[i][j] = table[i][j]
    elif b % 2 == 1:
        matrix = solve(b//2)
        r = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                r[i][j] = sum(matrix[i][t] * matrix[t][j] for t in range(n)) % 1000
        for i in range(n):
            for j in range(n):
                rtn[i][j] += sum(r[i][t] * table[t][j] for t in range(n)) % 1000
    else:
        matrix = solve(b//2)
        for i in range(n):
            for j in range(n):
                rtn[i][j] = sum(matrix[i][t] * matrix[t][j] for t in range(n)) % 1000

    for i in range(n):
        rtn[i] = list(map(lambda x:x%1000, rtn[i]))
    return rtn

n, b = map(int, input().split())
table = [list(map(int, input().split())) for _ in range(n)]
ans = solve(b)
for a in ans:
    print(*a)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다