행렬 제곱 (백준 10830번)

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

 

문제 풀이

행렬을 제곱하기 위해서 B번 곱하면 시간 초과

 

분할 정복하여 log_B으로 제곱 연산 수행 (B번 -> log_B번으로 축소 가능)

최종 시간 복잡도 O(N^3 logB)

 

import java.util.*;

public class Main {
    static int N;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        long B = sc.nextLong();
        long[][] matrix = new long[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = sc.nextLong();
            }
        }
        long[][] ans = pow(matrix, B);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sb.append(ans[i][j] % 1000).append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }

    static long[][] multiply(long[][] A, long[][] B) {
        long[][] C = new long[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    C[i][j] += A[i][k] * B[k][j];
                }
                C[i][j] %= 1000;
            }
        }
        return C;
    }

    static long[][] pow(long[][] A, long exp) {
        if (exp == 1) {
            return A;
        }

        long[][] half = pow(A, exp / 2);
        long[][] result = multiply(half, half);

        if (exp % 2 == 1) {
            result = multiply(result, A);
        }

        return result;
    }
}