[BOJ/Java] 10830. 행렬 제곱

[BOJ/Java] 10830. 행렬 제곱

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

---

문제 해석

행렬 제곱 문제는 주어진 정사각 행렬 \(A\)를 \(B\)번 거듭제곱한 결과를 구하는 문제이다. 단, 각 원소는 \(1,000\)으로 나눈 나머지를 출력해야 한다. 이 문제는 행렬의 거듭제곱을 효율적으로 계산하기 위해 **분할 정복(Divide and Conquer)**과 **행렬 곱셈**을 활용해야 한다.

풀이 과정

1. 행렬 곱셈 구현: 두 행렬을 곱하는 함수를 구현한다. 이때, 곱셈 결과의 각 원소는 \(1,000\)으로 나눈 나머지를 저장한다.
2. 분할 정복을 이용한 거듭제곱: 행렬 \(A\)를 \(B\)번 거듭제곱할 때, \(B\)가 짝수인 경우와 홀수인 경우로 나누어 재귀적으로 계산한다:
   • \(B\)가 짝수인 경우: \(A^B = (A^{B/2}) \times (A^{B/2})\)
   • \(B\)가 홀수인 경우: \(A^B = A \times (A^{B-1})\)
3. 기저 조건: \(B = 1\)인 경우, 행렬 \(A\)를 그대로 반환한다.
4. 결과 출력: 최종적으로 계산된 행렬을 출력한다.

코드

import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = 1000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 행렬의 크기
        long B = Long.parseLong(st.nextToken()); // 거듭제곱 횟수

        int[][] matrix = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken()) % MOD;
            }
        }

        // 행렬 거듭제곱 계산
        int[][] result = pow(matrix, B);

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sb.append(result[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }

    // 행렬 곱셈 함수
    static int[][] multiply(int[][] a, int[][] b) {
        int N = a.length;
        int[][] result = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    result[i][j] = (result[i][j] + a[i][k] * b[k][j]) % MOD;
                }
            }
        }
        return result;
    }

    // 분할 정복을 이용한 행렬 거듭제곱 함수
    static int[][] pow(int[][] matrix, long exponent) {
        int N = matrix.length;
        int[][] result = new int[N][N];

        // 단위 행렬로 초기화
        for (int i = 0; i < N; i++) {
            result[i][i] = 1;
        }

        while (exponent > 0) {
            if (exponent % 2 == 1) {
                result = multiply(result, matrix);
            }
            matrix = multiply(matrix, matrix);
            exponent /= 2;
        }
        return result;
    }
}

시간 복잡도 분석

시간 복잡도는 \(O(N^3 \log B)\)이다. 행렬 곱셈은 \(O(N^3)\)의 시간이 소요되며, 거듭제곱은 \(O(\log B)\)번 수행되기 때문이다. 이는 문제의 제약 조건 내에서 효율적으로 동작한다.

느낀점

이 문제는 분할 정복과 행렬 곱셈을 결합하여 행렬의 거듭제곱을 효율적으로 계산하는 방법을 배울 수 있는 좋은 문제이다. 특히, 큰 지수에 대한 거듭제곱을 빠르게 계산하는 방법을 이해하는 데 도움이 되었다. 이러한 문제는 선형대수나 알고리즘 최적화에서 자주 활용될 수 있을 것 같다.