백준 10830 행렬제곱 Java [분할 정복]

https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱

행렬 A의 B제곱 행렬을 구해야한다

B의 숫자가 1000억이므로 Long타입으로 써야하고, 완전탐색으로 하면 안된다

 

제곱을 생각해보면 A^5 = A^4 * A^1 성립한다

A^c = A^a * A^b로 일반화할 수 있고 c = a + b이다

B를 100이라고 가정할때 2의 제곱수로 위에 일반화한 식으로 표현하면 64(2^6) + 32(2^5) + 4(2^2)

 

B를 2로 나눠서 몫이 1일때만 A의 제곱수를 곱하면 최대 36번 안에 계산된다

package gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {
    static int N;
    static long B;
    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());
        B = Long.parseLong(st.nextToken());
        int[][] arr = new int[N][N];
        for(int n = 0; n < N; n++) {
            arr[n] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

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

        result = calc(arr, result);

        for(int[] r : result) {
            System.out.println(Arrays.stream(r).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
        }
    }

    static int[][] multiply(int[][] arr1, int[][] arr2) {
        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] += arr1[i][k] * arr2[k][j];
                }
                result[i][j]%=1000;
            }
        }
        return result;
    }

    static int[][] calc(int[][] arr, int[][] result) {
        if (B == 0L) return result;
        if (B % 2 == 1L) result = multiply(arr, result);
        B /= 2;
        return calc(multiply(arr,arr), result);
    }
}

 

문제풀면서 주의해야할점은 처음에 1000이 들어왔을때 0으로 바꿔줘야하고,

B가 int로 담을 수 없는 큰 수가 오는 경우가 있어 long으로 담아야한다