[백준] 10830번 : 행렬 제곱 (java)

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

10830번: 행렬 제곱

어떻게 생각하고 문제를 풀었는가?

NxN 행렬 A의 B제곱은 x1+x2+....=B를 만족하는 A의 xi제곱들을 곱하여 나타낼 수 있습니다.

이때 xi의 값들이 2의 제곱으로 나타내어질 수 있도록 한다면 A의 제곱, 4제곱, 8제곱을 구하여 결과를 빠르게 구할 수 있습니다.

이러한 xi 값들은 B를 2진수로 표현하여 1을 갖는 자리를 확인함으로써 빠르게 찾아낼 수 있을 것이라고 생각하였습니다.

코드

import java.io.*;
import java.util.*;

class Main {
    private static int N;
    private static String bitmask;
    private static int[][] A;
    
    public static void main(String[] args) throws IOException {
        readInput();
        int[][] result = calculate();
        printMatrix(result);
    }

    private static void readInput() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        N = Integer.parseInt(tokenizer.nextToken());
        long B = Long.parseLong(tokenizer.nextToken());
        bitmask = Long.toBinaryString(B);
        A = new int[N][N];
        for(int i=0; i<N; i++){
            tokenizer = new StringTokenizer(reader.readLine());
            for(int j=0; j<N; j++){
                A[i][j] = Integer.parseInt(tokenizer.nextToken());
            }
        }
        reader.close();
    }

    private static int[][] calculate(){
        int[][] result = new int[N][N];
        for(int i=0; i<N; i++){
            result[i][i] = 1;
        }

        int index = bitmask.length()-1;
        for(int i=0; i<bitmask.length(); i++){
            if(i>0){
                A = multiple(A, A);
            }

            if(bitmask.charAt(index--) == '1'){
                result = multiple(result, A);
            }
        }

        return result;
    }

    private static int[][] multiple(int[][] from, int[][] to){
        int[][] result = 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++){
                    result[i][j] += from[i][k] * to[k][j];
                }
                result[i][j] = result[i][j] % 1000;
            }
        }
        return result;
    }
    
    private static void printMatrix(int[][] target){
        StringBuilder stringBuilder = new StringBuilder();
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                stringBuilder.append(target[i][j]);
                stringBuilder.append(" ");
            }
            stringBuilder.append("\n");
        }
        System.out.println(stringBuilder);
    }
}

B를 2진수로 만들어 필요한 A의 행렬 제곱을 계산하고, 결과에 곱하는 코드를 작성하였습니다.

주어진 문제에서 결과는 1000을 나눈 나머지의 값으로 원소를 표현해야 하는데, 주어진 입력이 1000이 될 경우를 미리 해결하여야 합니다.

이를 해결하고자 초기 행렬을 단위 행렬로 정의하고, 2^0부터 행렬 곱셈을 수행하도록 하였습니다.

행렬 곱셈을 하는 함수 multiple에서 행렬 곱셈의 결과를 다시 1000으로 나눈 나머지 값들로 선언하기 때문에 모든 결과는 1000보다 작은 값을 가질 수 있습니다.