[BOJ/JAVA] 10830번: 행렬 제곱

10830번: 행렬 제곱

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

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

키워드

• 크기가 N*N인 행렬 A가 주어진다.

• A의 B제곱을 구하는 프로그램

---

구현

• matrixMultiply
  • 두 정방행렬의 곱을 구하는 메소드
  • 시간복잡도
    • O(N^3)
  • 정방행렬의 곱은 다음과 같다.

    $$\begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix} * \begin{bmatrix} b_1 & b_2 \\ b_3 & b_4 \end{bmatrix} = \begin{bmatrix} a_1b_1+a_2b_3 & a_1b_2+a_2b_4 \\ a_3b_1+a_4b_3 & a_3b_2+a_4b_4 \end{bmatrix}$$

• calcMatrix
  • 분할정복을 이용한 행렬을 제곱하는 메소드
  • 제곱수를 절반으로 줄여가며 계산을 진행한다.

    $$\begin{aligned} a^b &= a^{b\over 2}*a^{b\over2} \qquad(n이\,짝수)\\ a^b &= a^{b\over 2}*a^{b\over2}*a^1\qquad(n이\,홀수)\\ \end{aligned}$$

  • 제곱수가 2라면 matrixMultiply 메소드를 호출하여 제곱 계산을 한다.
  • 제곱수가 1이라면 matrix를 반환한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class java_10830 {
    static int N;
    static long B;

    static int original[][];

    final static int MOD = 1000;

    static int[][] matrixMultiply(int matrixA[][], int matrixB[][]) {
        int nextMatrix[][] = new int[N][N];

        // 제곱하기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int sum = 0;

                for (int k = 0; k < N; k++) {
                    int tmp = (matrixA[i][k] * matrixB[k][j]) % MOD;
                    sum += tmp;
                }

                nextMatrix[i][j] = sum % MOD;
            }
        }

        return nextMatrix;
    }

    static void printResult(int result[][]) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(result[i][j] % MOD + " ");
            }
            System.out.println();
        }
    }

    // 분할정복을 이용한 행렬제곱
    static int[][] calcMatrix(int matrix[][], long exp) {
        // 1은 그냥 반환
        if (exp == 1) {
            return matrix;
        }

        // 2는 그냥 제곱하기
        if (exp == 2) {
            return matrixMultiply(matrix, matrix);
        }

        int resultMatrix[][] = calcMatrix(matrix, exp / 2);
        resultMatrix = matrixMultiply(resultMatrix, resultMatrix);

        if (exp % 2 != 0) {
            resultMatrix = matrixMultiply(resultMatrix, original);
        }

        return resultMatrix;
    }

    static void solution() {
        int result[][] = calcMatrix(original, B);

        printResult(result);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        B = Long.parseLong(st.nextToken());

        original = new int[N][N];

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

        // 제곱하는 메소드
        solution();

        br.close();
    }
}

---

Uploaded by N2T