Don't give up!

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

Coding Test/BOJ

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

Heang Lee 2021. 8. 18. 16:34

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

 

10830번: 행렬 제곱

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

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

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보다 작은 값을 가질 수 있습니다.

'Coding Test > BOJ' 카테고리의 다른 글

[백준] 1300번 : K번째 수 (java)  (0) 2021.08.20
[백준] 1541번 : 잃어버린 괄호 (java)  (0) 2021.08.17
[백준] 11758번 : CCW (java)  (0) 2021.08.16