[백준] BOJ_10830 행렬 제곱

1.문제 요약

• N×N 크기의 행렬 A를 B번 제곱한 결과를 구하는 문제

2.접근 방식

• 분할 정복을 이용한 거듭제곱 방식

단순히 행렬을 B번 곱하면 약 1000억 번의 연산이 필요하기 때문에 시간 초과가 발생합니다. 분할 정복을 사용하게 되면 시간 복잡도를 크게 줄일 수 있습니다.

• B가 짝수인 경우: (A^(B/2))²
• B가 홀수인 경우: A × (A^(B/2))²
• B == 1: A 반환

예를 들어 B = 5인 경우, B의 값이 5 -> 2 -> 1로 되며 A A^2 A^2 = A^5가 되어 매번 계산하는 방식보다 효율적인 방식으로 처리할 수 있습니다.

3.제출 코드

풀이 방식: 분할 정복 + 행렬 곱셈 + 모듈러 연산

package baekjoon.math;

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

public class BOJ_10830 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int[][] A = new int[N][N];
        long B = Long.parseLong(st.nextToken());

        // 입력 시점에 1000으로 나눈 나머지를 저장
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                A[i][j] = Integer.parseInt(st.nextToken()) % 1000;
            }
        }

        // 분할 정복으로 행렬 거듭제곱 계산
        int[][] answer = recursion(A, B, N);
        for (int[] a1 : answer) {
            for (int a2 : a1) {
                System.out.print(a2 + " ");
            }
            System.out.println();
        }
    }

    // 분할 정복을 이용한 행렬 거듭제곱
    private static int[][] recursion(int[][] A, long B, int N) {
        if (B == 1)
            return A;

        // A^(B/2) 계산
        int[][] half = recursion(A, B / 2, N);

        // B가 짝수: (A^(B/2))^2
        if (B % 2 == 0) {
            return calculate(half, half, N);
        } 
        // B가 홀수: A × (A^(B/2))^2
        else {
            return calculate(calculate(half, half, N), A, N);
        }
    }

    // 행렬 곱셈 수행
    private static int[][] calculate(int[][] A, int[][] B, int N) {
        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] += A[i][k] * B[k][j];
                    result[i][j] %= 1000;  // 중간 계산마다 모듈러 연산
                }
            }
        }
        return result;
    }
}

4.회고

• 자료구조: 2차원 배열
• 알고리즘: 분할 정복, 행렬 곱셈(수학)
• 느낀점: 재귀, 분할 정복같은 문제를 자주 풀어야 실력이 늘것같다.

문제 링크: https://www.acmicpc.net/problem/10830