[백준 알고리즘] - 행렬 제곱 (10830) with Python

📎 간략한 문제 정리

• N by N 행렬 A가 주어질 때, A의 B제곱을 구하는 프로그램을 작성하는 문제입니다.

📈 문제 분석

• 곱셈 연산을 거듭제곱하는 문제이므로 백준 알고리즘의 곱셈(1629번) 풀이 를 참고할 필요가 있습니다.

🙋‍♂️ 내가 처음 생각한 해결 방법

• 분할 정복을 활용합니다.

💻 풀이한 코드

from sys import stdin

input = stdin.readline
a, b = map(int, input().split())
matrix = [list(map(lambda x: x % 1000, map(int, input().split()))) for _ in range(a)]

def power(m, y):
    if y == 1:
        return m
    partial = power(m, y // 2)
    partial_square = multiply_matrix(partial, partial)
    if y % 2 == 0:
        return partial_square
    elif y % 2 == 1:
        return multiply_matrix(partial_square, m)


def multiply_matrix(matrix_1, matrix_2):
    length = len(matrix_1)
    result = [[0 for _ in range(length)] for _ in range(length)]
    for i in range(length):
        for j in range(length):
            result[i][j] = sum([(matrix_1[i][k] * matrix_2[k][j])%1000 for k in range(length)])%1000
    return result

answer = power(matrix, b)
for i in range(a):
    print(' '.join(map(str, answer[i])))

📝 해결 과정에서 만난 문제, 고민들

• 집중을 못해서인지 매우 쉬운문제임에도 불구하고 굉장히 오래 고민했습니다. 메소드 구현에서 뜬금없는 변수를 넣거나 마지막 출력문을 정답 규격에 맞지 않고 개인적인 확인을 위해 만들어둔 상태로 테스트하여 계속 틀렸습니다가 반복되었습니다. 의외로 이런 곳에서 틀릴 수 있기 때문에 항상 입력과 출력을 경계해야할 필요가 있습니다.
• 파이썬의 경우 int의 범위가 부족할 경우 자동으로 long 타입으로 변환되기 때문에 문제가 없지만 다른 사람들이 풀이한 C++ 등의 풀이를 보면 해당 오류가 많이 발생했음을 알 수 있습니다. 주어진 범위가 매우 넓기 때문에 int안에 해당 숫자를 할당하는 것만으로도 오류가 발생할 수 있습니다. 입출력의 범위를 디테일하게 체크할 필요가 있습니다.
• map 함수 자체가 iterable하므로 어떤 리스트에 여러 연산을 적용하고 싶으면 map 안에 map을 구현하는 구조로 작성할 수 있습니다.

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