행렬의 거듭 제곱 구하기(난이도: 하)

1. 문제 설명

(1) 크기가 N*N인 행렬 A가 주어진다. 이때,  A^B를 구하는 프로그램을 작성한다.

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 2 <= N <= 5, 1 <= B <= 100,000,000,000으로 제한한다.

 

출력 조건

(1) 원소가 크면 문제가 발생할 수 있으므로, A^B의 원소를 1000으로 나눈 나머지를 출력한다.

 

 

입력 예제

3

2 5                  <-- 행렬 크기와 지수

1 2

3 4

3 3                  <-- 행렬 크기와 지수

1 2 3

4 5 6

7 8 9

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

 

출력 예제

69 558

337 406

 

468 576 684

62 305 548

656 34 412

 

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

 

 

 

 

3. 제약 조건

X

 

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

(1) 지수가 1인 상태

 

 

 

 

6. 코드

public class MatrixPow {
    // 홀수를 위한 복사 행렬과 행령의 크기 
    private static int[][] Matrix;
    private static int N;

    // 출력을 위한 변수
    private static StringBuilder sb = new StringBuilder();

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

        int C = Integer.parseInt(sc.readLine());
        for(int i=0; i<C; i++) {
            st = new StringTokenizer(sc.readLine());
            N = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int[][] A = new int[N][N];

            // 행렬에 값을 넣는 과정
            for(int y=0; y<N; y++) {
                st = new StringTokenizer(sc.readLine());
                for(int x=0; x<N; x++) {
                    A[y][x]= Integer.parseInt(st.nextToken());
                }
            }
            // 홀수가 나오면 사용하는 행렬
            // 예) 2^7 = (2^6)*MATRIX
            Matrix = A;

            // 주요 메서드 실행과 동시에 값 저장
            writeArr(solve(A, B));
        }
        System.out.println(sb);
    }

    // 거듭제곱 행렬을 수행하기 위해
    // 분할 정복하는 주요 메서드
    private static int[][] solve(int[][] a, int b) {

        // 기저사례(1): 지수가 1이라면 바로 행렬 리턴
        if(b==1) return a;

        // 분할 시작
        int[][] ret = solve(a, b/2);

        // 행렬 곱 수행
        ret = multiplyMatrix(ret, ret);

        // 홀수라면 아까 위해서 말했던 Matrix 곱
        if(b%2==1) ret = multiplyMatrix(ret, Matrix);

        return ret;
    }

    // a와 b 행렬을 서로 곱셈을 수행하는 메서드
    private static int[][] multiplyMatrix(int[][] a, int[][] b){
        int[][] ret = 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++) {
                    ret[i][j]+=a[i][k]*b[k][j];
                }
            }
        }
        return ret;
    }

    // 거듭제곱의 결과를 %1000으로 수행하여 출력하는 메서드
    private static void writeArr(int[][] a) {
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                sb.append((a[i][j]%1000) +" ");
            }
            sb.append("\n");
        }
        sb.append("\n");
    }
}

 

( 여기서 왜 홀수를 절반으로 안 나누고 짝수를 구한 후 홀수를 곱하는 지 의문이 들 수 있다. )

( 그 이유는 아래의 그림처럼 만약 홀수까지 나누게 되면, 결국 홀수의 부분문제와 짝수의 부분문제에서

호출의 발생이 중복되는 경우가 많기 때문이다. )

 

( 이렇게 되면 지수 크기가 커질수록 선형적으로 증가하게 된다. ) 

 

( 그러나, 아래의 그림처럼 짝수만 나눠준다면 호출의 발생이 중복되지 않으며, O(lgN)개 만큼 호출하게 된다. )