[JAVA]백준 10830번: 행렬 제곱

www.acmicpc.net/problem/10830

10830번: 행렬 제곱

1. 문제 설명

 

크기가 N*N 행렬 A가 주어질 때 A의 B제곱을 구하는 문제이다.

답은 각 원소를 1000으로 나눈 나머지를 출력한다.

 

2. 풀이

 

B의 범위가 1 <=B <=100,000,000,000이기에 완전 탐색 같은 방법으로 풀게 된다면 시간 초과가 날 것이다.

 

따라서 분할정복으로 풀어야 하는 문제이다.

 

B를 base case가 1인 경우까지 2로 분할한 후, 곱셈을 통해 답을 병합해가면 된다. 

 

 

 

 

3. 코드

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

public class Main {

    public static int[][] procession;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 행렬 사이즈
        int procession_size;
        // 제곱수
        long squared;
        StringTokenizer input = new StringTokenizer(br.readLine());

        procession_size = Integer.parseInt(input.nextToken());
        squared = Long.parseLong(input.nextToken());

        // 행렬 저장
        procession = new int[procession_size][procession_size];


        // 행렬 입력
        for (int x = 0; x < procession_size; x++) {
            StringTokenizer procession_input = new StringTokenizer(br.readLine());

            for (int y = 0; y < procession_size; y++) {
                procession[x][y] = Integer.parseInt(procession_input.nextToken());
            }
        }

        // 함수 호출
        int[][] answer = Divide_procession(squared);

        
        for (int x = 0; x < procession_size; x++) {
            for (int y = 0; y < procession_size; y++) {
                bw.write(String.valueOf(answer[x][y]%1000) + " ");
            }
            bw.write("\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    public static int[][] Divide_procession(long num) {
        // base case
        if (num == 1) {
            return procession;
        }

        int[][] temp = Divide_procession(num / 2);

        if (num % 2 == 0) {
            return Cal_procession(temp, temp);
        } else {
            return Cal_procession(Cal_procession(temp, temp), procession);
        }

    }

    // 행렬 곱셈 계산
    public static int[][] Cal_procession(int[][] one,int[][] two) {
        int size = one[0].length;

        int[][] temp = new int[size][size];

        for (int x = 0; x < size; x++) {

            for (int y = 0; y < size; y++) {

                int sum = 0;

                for (int z = 0; z < size; z++) {
                    sum = (sum + one[x][z] * two[z][y]) % 1000;
                }

                temp[x][y] = sum;
            }
        }

        return temp;

    }
}