[백준] 10830 행렬 제곱 (JAVA)

✉️문제

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

10830번: 행렬 제곱

 

📝 접근

1. B의 범위를 보면 int형 범위가 넘어간다. 따라서 long으로 선언해야 한다.

2. 행렬 배열은 int형으로 선언해도 된다. (제곱하고 각 원소를 1000으로 나누기 때문)

3. 제곱을 100,000,000,000번 하면 시간제한인 1초 안에 풀 수 없다. 따라서 분할 정복법을 이용한다. 

 

 

🗝 문제풀이

package baekjoon;

import java.util.Scanner;

public class B10830 {

    static int n;
    static long b;
    static final int DIV = 1000;
    static int[][] matrix;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt(); // 행렬 크기
        b = sc.nextLong(); // 제곱

        // 행렬 수 입력받기
        matrix = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
            // 행렬의 각 원소는 1000이하의 자연수인데,
            // b가 1인 경우 pow함수를 거치지 않기 때문에
            // 1000이라는 수가 나머지 연산을 하지 않는다. 따라서 미리 나머지 연산을 해준다.
                matrix[i][j] = sc.nextInt() % DIV; 
            }
        }

        int[][] answer = solution(matrix,b);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                System.out.print(answer[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static int[][] pow(int[][] arr, int[][] arr2) {
        // 매개변수로 넘어 온 배열에 영향을 주지 않기 위해 새로운 배열 선언
        int[][] tmp = new int[n][n];

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                int num = 0;
                for(int k = 0; k < n; k++) {
                    num += arr[i][k] * arr2[k][j];
                    num %= DIV;
                }
                tmp[i][j] = num;
            }
        }

        return tmp;
    }

    public static int[][] solution(int[][] arr, long exp) {
        // 지수가 1이면 그대로 리턴
        if(exp == 1L) return arr;

        // 분할 정복
        int[][] tmp = solution(arr, exp / 2);

		// 거듭제곱 계싼
        tmp = pow(tmp, tmp);

        // 홀수이면 처음 입력 받은 매트릭스를 곱해준다.
        if(exp % 2 == 1L) {
            tmp = pow(tmp, matrix);
        }

        return tmp;
    }
}