백준 10830 행렬 제곱 Java: 이진 거듭제곱과 모듈러 행렬 곱셈

백준 10830번 ‘행렬 제곱’은 지수 B가 최대 1,000억이므로 행렬을 B번 곱할 수 없다. 정수 거듭제곱과 마찬가지로 지수를 이진수로 보면서 제곱해 O(log B)번의 행렬 곱셈으로 줄여야 한다.

• 백준 10830번 행렬 제곱

행렬 이진 거듭제곱

지수의 각 bit를 낮은 자리부터 확인한다.

1. 결과 행렬을 항등 행렬 I로 시작한다.
2. 현재 지수가 홀수면 결과에 현재 base 행렬을 곱한다.
3. base를 제곱한다.
4. 지수를 2로 나누고 0이 될 때까지 반복한다.

예를 들어 B = 5는 이진수 101이다. 필요한 거듭제곱은 A¹과 A⁴이므로 두 bit에 해당하는 행렬만 결과에 반영한다.

행렬 곱셈은 결합법칙이 성립하므로 곱셈 순서의 괄호를 바꿔 제곱을 재사용할 수 있다. 그러나 정사각 행렬끼리도 일반적으로 교환법칙 AB = BA는 성립하지 않는다. 이 알고리즘의 근거는 교환법칙이 아니라 결합법칙이다.

모듈러를 매 곱셈에 적용하는 이유

문제는 각 원소를 1,000으로 나눈 나머지를 요구한다. 다음 성질을 이용하면 중간 결과도 계속 줄일 수 있다.

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a × b) mod m = ((a mod m) × (b mod m)) mod m

입력 원소가 정확히 1,000이고 B = 1인 경우도 0을 출력해야 하므로, 입력 단계에서부터 % 1000을 적용한다.

Java 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static final int MOD = 1000;

    private static int[][] multiply(int[][] left, int[][] right) {
        int size = left.length;
        int[][] result = new int[size][size];

        for (int row = 0; row < size; row++) {
            for (int column = 0; column < size; column++) {
                long sum = 0;

                for (int middle = 0; middle < size; middle++) {
                    sum += (long) left[row][middle]
                            * right[middle][column];
                }

                result[row][column] = (int) (sum % MOD);
            }
        }

        return result;
    }

    private static int[][] identity(int size) {
        int[][] result = new int[size][size];

        for (int index = 0; index < size; index++) {
            result[index][index] = 1;
        }

        return result;
    }

    private static int[][] power(int[][] matrix, long exponent) {
        int[][] result = identity(matrix.length);
        int[][] base = matrix;

        while (exponent > 0) {
            if ((exponent & 1L) == 1L) {
                result = multiply(result, base);
            }

            base = multiply(base, base);
            exponent >>= 1;
        }

        return result;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        int size = Integer.parseInt(tokenizer.nextToken());
        long exponent = Long.parseLong(tokenizer.nextToken());
        int[][] matrix = new int[size][size];

        for (int row = 0; row < size; row++) {
            tokenizer = new StringTokenizer(reader.readLine());

            for (int column = 0; column < size; column++) {
                matrix[row][column] = Integer.parseInt(
                        tokenizer.nextToken()
                ) % MOD;
            }
        }

        int[][] answer = power(matrix, exponent);
        StringBuilder output = new StringBuilder();

        for (int row = 0; row < size; row++) {
            for (int column = 0; column < size; column++) {
                if (column > 0) {
                    output.append(' ');
                }
                output.append(answer[row][column]);
            }
            output.append('\n');
        }

        System.out.print(output);
    }
}

예제 실행

2 5
1 2
3 4

69 558
337 406

multiply()는 호출할 때마다 0으로 초기화된 새 결과 행렬을 만든다. 기존 결과 행렬에 다음 곱셈 값을 누적하면 이전 계산이 섞여 전혀 다른 행렬이 된다.

한 시간 동안 막혔던 이유

원문에서는 정수 거듭제곱과 행렬 곱셈을 조합해야 한다는 방향까지는 잡았지만, 정사각 행렬이면 교환법칙도 성립한다고 잘못 정리했다. 교환법칙은 필요하지 않고 실제로 일반적인 정사각 행렬에서도 성립하지 않는다.

구현에서는 새 행렬이 아니라 이미 값이 든 행렬에 곱셈 결과를 계속 더해 답이 나오지 않았고, 약 한 시간 뒤에야 누적 대상을 분리했다고 적혀 있다. 이 문제에서 각 행렬 곱셈의 output을 새 배열로 만드는 이유가 단순한 style이 아니라 정확성 조건인 셈이다.

정수 이진 거듭제곱과 모듈러의 기초는 백준 1629 곱셈, 행렬 곱셈의 순서가 비용을 바꾸는 문제는 백준 11049 행렬 곱셈 순서에서 이어서 볼 수 있다.

복잡도와 overflow

한 번의 행렬 곱셈은 O(N³)이고 곱셈 횟수는 O(log B)이므로 전체 시간 복잡도는 O(N³ log B)다. 결과와 base 행렬을 저장하는 추가 공간은 O(N²)이다.

각 항은 1,000 미만으로 유지되지만 곱셈과 합의 중간값은 long으로 계산해 overflow 여지를 줄였다. 문제의 N ≤ 5 범위에서는 충분히 안전하고, 마지막에만 1,000으로 나눠 int에 저장한다.

Java source를 수동 검토하고 보존된 세 예제, B = 1, 원소 1,000, 작은 random 행렬 120개를 반복 곱셈 oracle과 대조했다. 2026년 8월 2일 현재 BOJ URL은 채점 서비스 준비 화면이라 current judge 재제출은 확인하지 못했다.