골드에그

1. 문제요약

10830번: 행렬 제곱 (acmicpc.net)

행렬 A 에 대한 B 제곱을 구하시오. 이 때 각 원소는 1000으로 나눈 나머지를 출력하여야 된다.

2. 문제예제

3. 문제풀이(수동)

문제풀이는 생략한다. 중학교 때 배운 행렬의 곱셈 연산이다.

4. 팩트추출

Fact 1 : 전형적인 분할정복 문제이다. 행렬을 하나씩 계속 곱해서 문제를 풀 수 있지만, 그렇게 하면 O(B) 크기만큼 소요된다.

A X A X A ... ( B 제곱만큼 )

이 문제는 부분 문제이며 결과 값들이 서로 독립이므로 분할 정복으로 문제를 풀 수 있다.

이전 결과 값이 다음 결과 값에 영향을 미쳐 문제가 중첩된다면 DP 점화식으로 문제를 풀어야 하겠지만, 여기서는 독립이기 때문에 분할 정복 알고리즘으로 불린다. DP 와 분할 정복의 차이점은 아래 링크를 참고하자.

[개념] DP (Dynamic Programming) :: 골드에그 (tistory.com) DP 특징 3번 참고.

B 가 9 라면,

{( A X A ) X ( A X A )} X {( A X A ) X ( A X A )} X A

=> A X A

=> {( A X A ) X ( A X A )}

=> {( A X A ) X ( A X A )} X {( A X A ) X ( A X A )} 

=> {( A X A ) X ( A X A )} X {( A X A ) X ( A X A )} X A

로 4번만에 연산이 가능하다.

5. 문제전략

분할 정복 기초 문제이다.

6. 소스코드

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

public class Main {

    final static int MOD = 1000;
    public static int N;
    public static int[][] origin;

    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());
        long B = Long.parseLong(st.nextToken());

        origin = new int[N][N];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < N; j++) {
                origin[i][j] = Integer.parseInt(st.nextToken()) % MOD;
            }
        }
        int[][] result = pow(origin, B);

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                sb.append(result[i][j]).append(' ');
            }
            sb.append('\n');
        }
        System.out.println(sb);

    }
    public static int[][] pow(int[][] A, long exp) {
        if(exp == 1L) {
            return A;
        }
        int[][] ret = pow(A, exp / 2);
        ret = multiply(ret, ret);
        if(exp % 2 == 1L) {
            ret = multiply(ret, origin);
        }
        return ret;
    }
    private static int[][] multiply(int[][] matrix1, int[][] matrix2) {
        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] += matrix1[i][k] * matrix2[k][j];
                    ret[i][j] %= MOD;
                }
            }
        }
        return ret;
    }
}