[백분_분할정복] 10830번 - 행렬 제곱 - 이해까지 도와주는 풀이

 

 

문제

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

 

입력

 

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤  5, 1 ≤ B ≤ 100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

 

출력

 

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

 

예시 입력

2 5
1 2
3 4

 

 

예시 출력

69 558
337 406

 

 

풀이

이 문제는 크기가 N*N인 행렬 A를 B번 곱한 후, 각 원소를 1,000으로 나눈 나머지를 출력하는 문제입니다. 

 

큰 수 B를 고려하여, 이 문제를 해결하기 위해서는 행렬의 거듭제곱과 모듈러 연산을 조합하여 효율적으로 계산해야 합니다.

아래는 이 문제를 해결하는 접근 과정을 상세히 설명합니다.

1. 입력 받기
   - 먼저 첫째 줄에서 행렬의 크기 N과 B를 입력 받습니다.
   - 다음 N개의 줄에 걸쳐서 행렬 A의 각 원소를 입력 받습니다.

2. 행렬 거듭제곱 구현
   - 행렬 A를 B번 곱하는 것은 A를 B번 곱하는 연산을 수행하는 것과 동일합니다. 이때, B가 매우 큰 수일 수 있으므로 효율적인 방법이 필요합니다.

   - 분할 정복(Divide and Conquer)을 사용하여 행렬의 거듭제곱을 효율적으로 계산할 수 있습니다.

   - B를 절반으로 나눈 후, 절반으로 나눈 행렬에 대한 거듭제곱을 계산하고, 이를 다시 곱하는 방식으로 계산합니다. 이때, B가 홀수일 경우에는 추가적으로 A와의 곱셈이 필요합니다.

   - 중간 결과와 최종 결과의 각 원소를 1,000으로 나눈 나머지를 계산하여 나중에 출력할 때 사용합니다.

3. 모듈러 연산
   - 각 곱셈 과정과 최종 결과에 대해서 모듈러 연산을 수행합니다. 각 원소를 1,000으로 나눈 나머지를 저장하고, 출력할 때 사용합니다.

4. 결과 출력
   - 행렬의 B제곱을 계산한 최종 결과를 출력합니다.

 

소스코드

 

# 행렬 곱셈 함수 정의
def matrix_multiply(A, B, N):
    C = [[0] * N for _ in range(N)]  # 결과 행렬 초기화
    for i in range(N):
        for j in range(N):
            for k in range(N):
                C[i][j] += A[i][k] * B[k][j]  # 행렬 곱셈 계산
                C[i][j] %= 1000  # 각 원소를 1,000으로 나눈 나머지 계산
    return C

# 행렬 거듭제곱 함수 정의
def matrix_power_recursive(A, N, B):
    if B == 1:
        for i in range(N):
            for j in range(N):
                A[i][j] %= 1000  # 각 원소를 1,000으로 나눈 나머지 계산
        return A
    half_power = matrix_power_recursive(A, N, B // 2)  # 절반 지수에 대한 결과 계산
    result = matrix_multiply(half_power, half_power, N)  # 절반 지수 결과끼리 곱셈
    if B % 2 == 1:  # B가 홀수일 경우
        result = matrix_multiply(result, A, N)  # 추가로 A와의 곱셈 수행
    return result

# 입력 받기
N, B = map(int, input().split())  # 행렬 크기 N과 거듭제곱 B 입력
A = [list(map(int, input().split())) for _ in range(N)]  # 행렬 A 입력

# 행렬의 B제곱 계산
result = matrix_power_recursive(A, N, B)

# 결과 출력
for row in result:
    print(*row)