[백준] 행렬 제곱(10830)

문제

[백준] 행렬 제곱(10830)

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

입력

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)

출력

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

해설

백준 사이트 단계별로 풀어보기 탭 중 분할 정복에 분류되어있는 곱셈문제 + 행렬 곱셈문제의 응용 버전으로 두 문제를 풀이한 후에 도전하는 것을 추천합니다!

풀이

import java.util.*;
import java.io.*;

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

	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());

		long[][] matrix = new long[N][N];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				matrix[i][j] = Long.parseLong(st.nextToken());
			}
		}
		
		long[][] answer = pow(matrix, B);
		
		StringBuilder sb = new StringBuilder();
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				sb.append(answer[i][j]).append(" ");
			}
			sb.append("\n");
		}
		
		System.out.println(sb.toString());
	}

	public static long[][] pow(long[][] A, long exponent) {
		if (exponent == 1)
			return multiple(A);

		long[][] temp = pow(A, exponent / 2);

		if (exponent % 2 == 1)
			return multiple((multiple(temp, temp)), A);

		return multiple(temp, temp);
	}

	/* 오버로딩 */
	public static long[][] multiple(long[][] A) {
		long[][] result = new long[N][N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				result[i][j] = A[i][j] % MOD;
			}
		}

		return result;
	}

	public static long[][] multiple(long[][] A, long[][] C) {
		long[][] result = 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++) {
					result[i][k] += A[i][j] * C[j][k];
				}
			}
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				result[i][j] %= MOD;
			}
		}

		return result;
	}
}