[백준]#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제곱한 결과를 출력한다.

예제 입력 1

2 5
1 2
3 4

예제 출력 1

69 558
337 406

예제 입력 2

3 3
1 2 3
4 5 6
7 8 9

예제 출력 2

468 576 684
62 305 548
656 34 412

예제 입력 3

5 10
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1

예제 출력 3

512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512

풀이

이 문제는 단순한 행렬의 곱셈으로 보이지만 분할 정복을 이용해서 풀어야 하는 문제이다.

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

public class Main {
    static int N;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        long B = Long.parseLong(str[1]);
        int[][] A = new int[N][N];

        for(int i=0; i<N; i++) {
            String[] input = br.readLine().split(" ");
            for(int j=0; j<N; j++) {
                A[i][j] = Integer.parseInt(input[j]);
            }
        }

        int[][] res = solution(A, B);

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++)
                System.out.print(res[i][j]%1000+" ");
            System.out.println();
        }
    }

    static int[][] square(int[][] a, int[][] A) {
        int[][] temp = 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++) {
                    sum += a[i][k]*A[k][j];
                }
                temp[i][j] = sum%1000;
            }
        }

        return temp;
    }

    static int[][] solution(int[][] a, long b) {
        if(b==1)
            return a;
        else if(b%2==0) {
            int[][] temp = solution(a, b/2);
            return square(temp, temp);
        }
        else {
            return square(solution(a, b-1), a);
        }
    }
}