백준 10830번 : 행렬 제곱 | JAVA

 

📌 알고리즘 선택

이 문제는 단순히 하나의 행렬을 계속해서 곱해나가는 문제이지만, 그렇다고 행렬을 곱하는 연산만 구현한다면,, 시간초과가 날 것이다. 그렇기에 거듭제곱의 지수를 반으로 나누어가며 분할정복(dp)해야 효율적으로 연산할 수 있다.

지수를 반으로 나누는 형식의 분할정복 풀이법은 앞선 문제 '백준 11401번 이항계수 3'에서 구현한 적이 있기에 더욱 쉽게 문제를 해결할 수 있었다.

 

---

📌 풀이

전체적인 구현 흐름은 다음과 같다.

 

main()

1. 행렬의 크기 N과 지수 값 B 입력받기

   - (주의) 문제에서 B 값의 범위가 1 ≤ B ≤ 100,000,000,000 이므로, B의 타입에 유의해야 한다.

   - B의 타입을 long으로 하자.

2. 2차원의 행렬 입력받기

   - pow 함수에서 지수가 1인 경우 행렬을 그대로 출력하도록 했는데, 문제의 조건 중 각 원소를 1000으로 나눈 나머지를 출력해야 하는 조건이 있기 때문에, 행렬을 입력 받을 때부터 1000으로 나눈 나머지 값을 입력하도록 하자. (이는 모듈러 연산의 규칙에 의해 가능하다.)

3. 결과 행렬 출력하기

 

pow(행렬, 지수)

1. 지수가 1일 경우 입력받은 행렬 그대로 출력하기

2. 지수를 절반으로 분할하여 재귀호출하기

3. 절반으로 나뉜 행렬을 multiple() 함수를 이용하여 제곱하기

4. 지수가 홀수일 경우 원래 행렬 한번 더 곱해주기

 

multiple(행렬1, 행렬2)

1. 행렬 곱셈 구현하기

 

---

📌 코드

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

public class Main {

    static int N;
    static int P = 1000;
    static int[][] map;

    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());
        long B = Long.parseLong(st.nextToken());  // 타입 주의

        map = new int[N][N];

        // 행렬 입력
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken()) % P;
            }
        }

        // 행렬 거듭제곱
        int[][] result = pow(map, B);

        // 결과 출력
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                sb.append(result[i][j]).append(' ');
            }
            sb.append('\n');
        }

        System.out.println(sb);

    }

    public static int[][] pow(int[][] base, long expo) {

        //지수가 1일 경우
        if(expo == 1L)
            return base;

        // 지수를 절반으로 분할하여 재귀호출
        int[][] ret = pow(base, expo/2);

        // 절반으로 나뉜 행렬을 제곱
        ret = multiply(ret, ret);

        // 지수가 홀수라면
        // base^(expo/2) * base^(expo/2) * base 이다.
        if(expo % 2 == 1L)
            ret = multiply(ret, base);

        return ret;

    }

    public static int[][] multiply(int[][] o1, int[][] o2) {

        int[][] ret = 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++) {
                    ret[i][j] += o1[i][k] * o2[k][j];
                    ret[i][j] %= P;
                }
            }
        }

        return ret;
    }

}