[백준] 10830번: 행렬 제곱 - JAVA

🔗 문제 링크

BOJ 10830번: 행렬 제곱

10830번: 행렬 제곱

 

📝 풀이 과정

[백준] 1629번: 곱셈 - JAVA에서 확장된 문제다.

 

 

거듭제곱을 분할 정복으로 계산하는 같은 방식의 문제이지만, 행렬이라는 조건이 추가되었다. 행렬의 곱셈에서 A x B의 (i, j)의 값을 구하기 위해서는 A의 i열의 곱과 B의 j행의 곱을 순차적으로 더해 구해야 한다는 것을 이용해 곱셈하는 함수인 multipleMatrix(m1, m2)를 만들어 주었다.

 

기존 거듭제곱 문제에서는 거듭 제곱값으로 주어진 값이 0이면 1을 반환해 주었는데 행렬에서 곱셈의 값이 이전과 동일하려면 단위 행렬을 반환해야한다.

// N = 3
1 0 0
0 1 0
0 0 1

 

이를 활용해 주어진 수를 분할해가며 반복해서 제곱하면 된다.

 

 

💻 코드

import java.util.Scanner;

public class Main {
    static int MOD = 1000, N;
    static int[][] unitMatrix;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        long B = sc.nextLong();

        int[][] matrix = new int[N][N];
        unitMatrix = new int[N][N];

        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                matrix[i][j] = sc.nextInt() % MOD;

        for (int i = 0; i < N; i++)
            unitMatrix[i][i] = 1;

        matrix = powMatrix(B, matrix);

        for (int[] m : matrix) {
            for (int i : m)
                System.out.print(i + " ");
            System.out.println();
        }
    }

    static int[][] powMatrix(long n, int[][] matrix) {
        if (n == 0)
            return unitMatrix;
        if (n == 1)
            return matrix;

        int[][] nMatrix = powMatrix(n / 2, matrix);
        nMatrix = multipleMatrix(nMatrix, nMatrix);

        return n % 2 == 0 ? nMatrix : multipleMatrix(nMatrix, matrix);
    }

    static int[][] multipleMatrix(int[][] m1, int[][] m2) {
        int[][] matrix = 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++)
                    matrix[i][j] += (m1[i][k] * m2[k][j]) % MOD;
                matrix[i][j] %= MOD;
            }
        }

        return matrix;
    }
}

 

📊 제출 결과