백준 10830 파이썬

 

10830번: 행렬 제곱

 

풀지 못한 이유

1. 행렬 곱을 코드로 풀어내지 못함. 

2. 재귀를 적절히 활용하지 못함

3. 재귀 탈출 조건 만이라도 알았다면 풀이에 접근할 수 있었음

4. 마지막 조건 (1000 이하) 에 적절히 대처하지 못함.

 

---

풀이 

이 문제의 핵심은 DP 라고 하는데, 사실 행렬의 곱셈을 코드로 풀어내는 것 역시 핵심이라고 생각한다.

행렬의 곱셈은 이런식으로 진행된다. (1, 3) x (3, 1) 처럼 앞 행렬의 두번째 좌표(3) 와 뒷 행렬의 첫번째 좌표(3) 가 같아야 행렬의 곱이 이루어진다. 10년전 중학교 수학과정에서 배운 기억이 난다.

이를 코드로 풀어낼 때도 이 원리를 적용하는게 중요하다.

def matrix_mul(mat_a, mat_b):
    length = len(mat_a)
    temp = [[0] * length for _ in range(length)]
    for i in range(length):
        for j in range(length):
            for k in range(length):
                temp[i][j] += mat_a[i][k] * mat_b[k][j]
    return temp

여기서 temp 라는 원소가 모두 0인 임시 배열을 생성한다. temp 는 각 행렬의 곱셈의 결과를 리턴하고, 매번 matrix_mul() 이 호출될 때마다 초기화 된다. 즉 동일 행렬의 제곱을 temp 라는 이름으로 리턴하는 것이다.

 

 

 

 

코드

import sys


def matrix_mul(mat_a, mat_b):
    length = len(mat_a)
    temp = [[0] * length for _ in range(length)]
    for i in range(length):
        for j in range(length):
            for k in range(length):
                temp[i][j] += mat_a[i][k] * mat_b[k][j]
            temp[i][j] %= 1000
    return temp


def matrix_pow(original, n):
    if n == 1:
        return original
    if n % 2 == 0:
        temp = matrix_pow(original, n // 2)
        return matrix_mul(temp, temp)
    else:
        temp = matrix_pow(original, n - 1)
        return matrix_mul(temp, original)


read = sys.stdin.readline
N, M = map(int, read().split())
matrix = [list(map(int, read().split())) for _ in range(N)]
result = matrix_pow(matrix, M)
for row in result:
    for num in row:
        print(num % 1000, end=' ')
    print()