[백준] 10830번 : 행렬 제곱 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

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

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 이전에 해결했던 2740번 : 행렬 곱셈 문제와 1629번 : 곱셈 문제를 함께 고려하면 문제를 해결할 수 있다.

두 행렬을 곱하는 연산과 거듭제곱 연산을 분할 정복으로 해결하는 과정을 합치면 해결할 수 있다.

각 행렬의 원소를 1,000으로 나눈 나머지를 구하는 문제이므로 두 행렬을 곱하는 연산에서 결과를 1,000으로 나눈 나머지로 저장한다.

거듭제곱 연산에서는 1이면 기본 행렬을 반환하고, 1이 아닐 경우 짝수이면 두 행렬의 곱을 반환하고 홀수이면 두 행렬의 곱에 기본 행렬을 한 번 더 곱한 결과를 반환한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 행렬의 크기와 거듭제곱 횟수를 입력받는다. N, B = map(int, sys.stdin.readline().split())
3. 기본 행렬을 저장할 리스트를 생성한다. matrix = []
4. 행렬의 크기만큼 반복하며 행렬의 각 행을 입력받아 리스트로 변환한 후 기본 행렬 리스트에 추가한다. for _ in range(N): matrix.append(list(map(int, sys.stdin.readline().split())))
5. 두 행렬을 곱하는 함수를 생성한다. def matrix_mul(m1, m2)
   1. 두 행렬의 곱을 저장할 2차원 리스트를 생성한다. result = list( list(0 for _ in range(N)) for _ in range(N))
   2. 앞 행렬의 행과 뒷 행렬의 열을 각 지정하고 for i in range(N): for j in range(N)
      1. 곱셈 연산을 해야 하는 위치를 불러와 곱하여 결과에 더한다. for k in range(N): result[i][j] += m1[i][k] * m2[k][j]
      2. 최종 결과를 1,000으로 나눈 나머지를 저장한다. result[i][j] %= 1000
   3. 두 행렬의 곱의 결과를 반환한다. return result
6. 거듭제곱 연산 분할 정복으로 해결하는 함수를 생성한다. def divide(b)
   1. 만약 거듭제곱하는 지수가 1이면 그냥 기본 행렬을 반환한다. if (b == 1): return matrix
   2. 반면에 지수가 2 이상이면 else
      1. 지수를 2로 나눈 몫의 결과를 다시 거듭제곱 연산 함수에 넣어 결과를 저장한다. res = divide(b // 2)
      2. 만약 지수가 짝수이면 결과로 반환된 행렬을 곱한다. if (b % 2 == 0): return matrix_mul(res, res)
      3. 반면에 지수가 홀수이면 결과로 반환된 행렬을 곱하고 기본 행렬을 한 번 더 곱해준다. else: return matrix_mul(matrix_mul(res, res), matrix)
7. 최종 정답에 거듭제곱 연산의 결과를 저장한다. answer = divide(B)
8. 정답 리스트의 각 행렬을 불러와 for row in answer
   1. 행렬별 열의 값을 1,000으로 나눈 나머지를 한 줄에 출력한다. for col in row: print(col % 1000, end = ' ')
   2. 한 행의 결과를 출력했다면 줄 바꿈을 한다. print()

3. 소스코드

import sys

N, B = map(int, sys.stdin.readline().split())

matrix = []
for _ in range(N):
    matrix.append(list(map(int, sys.stdin.readline().split())))

        
def matrix_mul(m1, m2):
    result = list( list(0 for _ in range(N)) for _ in range(N))

    for i in range(N):
        for j in range(N):
            for k in range(N):
                result[i][j] += m1[i][k] * m2[k][j]

            result[i][j] %= 1000

    return result

def divide(b):
    if (b == 1):
        return matrix
    else:
        res = divide(b // 2)
        if (b % 2 == 0):
            return matrix_mul(res, res)
        else:
            return matrix_mul(matrix_mul(res, res), matrix)
        
answer = divide(B)
for row in answer:
    for col in row:
        print(col % 1000, end = ' ')
    print()