[백준 10830번] 행렬 제곱 (java)

10830번: 행렬 제곱

 

백준 2740번 : 행렬 곱셈을 응용한 문제이다. 

B의 범위가 매우 크기 때문에 단순히 2740번 문제에서 for문을 하나 더 추가해서 문제를 풀면 시간초과가 난다. 

 

이 문제는 행렬을 곱하는 똑같은 과정을 반복하기 때문에 이미 한번 계산한 결과는 다시 재사용하면 계산 횟수를 줄일 수 있다. 따라서 분할과 정복 방법으로 문제를 해결하였다.

 

만약 B가 짝수라면, B번 행렬을 곱한 결과는 B/2번 행렬을 곱한 결과 * B/2번 행렬을 곱한 결과가 된다.

이 때 B/2번 행렬을 곱한 결과는 한 번만 계산한 뒤, 두 번 곱해주면 된다.

 

B/2번 행렬을 곱한 결과는 B/4번 행렬을 곱한 결과 * B/4번 행렬을 곱한 결과가 된다.

이 때도 마찬가지로 B/4번 행렬을 곱한 결과는 한 번만 계산하면 된다.

 

만약 B가 홀수라면, B번 행렬을 곱한 결과는 B/2번 행렬을 곱한 결과 * (B/2+1)번 행렬을 곱한 결과가 된다.

이 때 B/2번 행렬을 곱한 결과(res)는 한 번만 계산한 후, res*res*A를 하면 된다.

 

 

전체 코드 :

	import java.io.*;
	public class n10830 {
	static int N;
	static long B;
	static int[][] A;
	static final int MOD = 1000;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	String[] input = br.readLine().split(" ");
	N = Integer.parseInt(input[0]);
	B = Long.parseLong(input[1]);
	A = new int[N][N];
	for (int i = 0; i < N; i++) {
	input = br.readLine().split(" ");
	for (int j = 0; j < N; j++) {
	A[i][j] = Integer.parseInt(input[j]) % MOD;
	}
	}
	int[][] res = solve(B);
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
	bw.write(res[i][j] + " ");
	}
	bw.write("\n");
	}
	bw.flush();
	}
	public static int[][] solve(long cnt) {
	if (cnt == 1) {
	return A;
	}
	int[][] res = solve(cnt / 2);
	if (cnt % 2 == 0) { // 짝수일 때
	return calculate(res, res);
	}
	else { // 홀수일 때
	int[][] res2 = calculate(res, A);
	return calculate(res, res2);
	}
	}
	public static int[][] calculate(int[][] A, int[][] B) {
	int[][] tmp = 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++) {
	tmp[i][j] += (A[i][k] * B[k][j]) % MOD;
	}
	tmp[i][j] %= MOD;
	}
	}
	return tmp;
	}
	}

view raw 10830.java hosted with ❤ by GitHub