백준 10830 - 행렬제곱 (Java)

https://www.acmicpc.net/problem/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

 

풀이

기본적으로 행렬의 곱셈 방법을 구현하면 되는데, 방법으로는 분할 정복을 사용해서 시간을 줄여야 한다. 또한 나머지 연산의 분배법칙을 생각했을 때, 그냥 매 연산에 MOD 연산을 진행해도 된다.

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

public class BJ_10830_행렬제곱 {
    static int N;
    static int[][] map;
    static int[][] result;
    static long B;
    static 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());
        N = Integer.parseInt(st.nextToken());
        B = Long.parseLong(st.nextToken());
        map = new int[N][N];
        int[][] newMap = new int [N][N];
        result = new int[N][N];
        for(int i=0; i<N; i++)
        {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++)
            {
                newMap[i][j] = Integer.parseInt(st.nextToken());
                newMap[i][j] %= MOD;
            }
        }
        map = newMap;
        result = pow(B);
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
            {
                System.out.print(result[i][j]+" ");
            }
            System.out.println();
        }
    }

    public static int[][] pow(long b)
    {
        if(b==1)
        {
            return map;
        }
        int[][] tmp = pow(b/2);
        int[][] tmpPow2 = multi(tmp,tmp);
        return b%2==0 ? tmpPow2:multi(tmpPow2,pow(1));
    }

    public static int[][] multi(int[][] a, int[][] b)
    {
        int[][] arr = 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++)
                {
                    arr[i][j] += a[i][k]*b[k][j];
                }
                arr[i][j] %= MOD;
            }
        }
        return arr;
    }
}