Baekjoon | Q.10830 - 행렬 제곱

10830번: 행렬 제곱

 행렬의 거듭 제곱을 구하는 문제이다.

import java.util.Scanner;

public class Main {
  static int N;
  static int[][] A;

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

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        int el = sc.nextInt();
        A[i][j] = el;
      }
    }

    sc.close();

    long[][] result = mul(B);

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        sb.append(result[i][j] % 1000 + " ");
      }
      sb.append("\n");
    }

    System.out.println(sb.toString());
  }


  public static long[][] mul(long b) {
    long[][] result = new long[N][N];
    long[][] temp = new long[N][N];

    if(b == 1) {
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          result[i][j] = A[i][j] % 1000;
        }
      }
    }else if(b % 2 == 0) {
      
      temp = mul(b/2);

      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          int el = 0;
          for (int k = 0; k < N; k++) {
            el += temp[i][k] * temp[k][j];
          }
          result[i][j] = el % 1000;
        }
      }
    }else {
      temp = mul(b-1);

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

 for문을 이용하여 하나 하나 곱하여 거듭제곱을 하는 방법도 있지만 분할 정복 기법을 이용하여 작은 문제로 나누어 생각해보도록 하자.

 

 A^5는 ((A^2)^2)*A 으로 나눌 수 있다. 제곱 수가 1 / 짝수 / 홀수인 각각의 경우를 생각해보자.

 - 1일 경우에는 1 제곱인 자기 자신을 그대로 반환한다.

 - 짝수일 경우에는 (제곱 수 / 2) 제곱을 해준 행렬를 각각 곱한다. ( A^(제곱수/2)는 재귀호출을 이용)

 - 홀수인 경우는 (제곱 수 - 1) 제곱을 해준 행렬과 1 제곱 행렬을 곱한다. ( A^(제곱수-1)는 재귀호출을 이용)

 

 문제를 처음 제출 했을 때 런타임 오류가 발생했다. 찾아보니 입력값의 범위가 자료형의 범위보다 커서 발생한 것이었다. B의 값이 100,000,000,000까지 입력될 수 있으므로 자료형을 int가 아닌 long으로 잡아주어야 한다.