170. 10830(행렬 제곱) - 자바

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

class Main {
	static int N;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] tmp1 = br.readLine().split(" ");
		N = Integer.parseInt(tmp1[0]);
		long B = Long.parseLong(tmp1[1]);
		long[][] A = new long[N][N];

		for (int i = 0; i < N; i++) {
			String[] tmp2 = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				A[i][j] = Integer.parseInt(tmp2[j]);
			}
		}

		remainder(A);

		for (long[] val1 : Pow(A, B)) {
			for (long val2 : val1) {
				sb.append(val2).append(" ");
			}
			sb.append("\n");
		}
		
		System.out.println(sb);
	}

	private static long[][] Pow(long[][] a, long B) {
		if (B == 1) {
			return a;
		}

		long[][] tmp = Pow(a, B / 2);

		if (B % 2 == 1) {
			return MatrixMul(MatrixMul(tmp, tmp), a);
		} else {
			return MatrixMul(tmp, tmp);
		}
	}

	private static long[][] MatrixMul(long[][] A, long[][] B) {
		long[][] C = 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++) {
					C[i][j] += A[i][k] * B[k][j];
				}
			}
		}

		remainder(C);
		return C;
	}

	private static void remainder(long[][] A) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				A[i][j] %= 1000;
			}
		}

	}
}

문제요약

행렬 곱을 진행하라(분할정복을 이용해서)

설명

일단 이 문제에서 B가 매우 큰 값을 받기 때문에 long을 사용하지 않으면 문제가 생긴다.

먼저 행렬의 곱셈은 다음으로 나타낼 수 있다.

제곱은 다음으로 나타낼 수 있다.

따라서 행렬의 곱셈은 

	private static long[][] MatrixMul(long[][] A, long[][] B) {
		long[][] C = 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++) {
					C[i][j] += A[i][k] * B[k][j];
				}
			}
		}

		remainder(C);
		return C;
	}

위와 같이 표현했다.

 

remailder는 1000의 나머지를 구하기 위해 사용해 준 것이다.

때문에 다음과 같이 나타낼 수 있다.

	private static void remainder(long[][] A) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				A[i][j] %= 1000;
			}
		}

	}

 

거듭제곱 또한 위에서 나타낸거 같이

	private static long[][] Pow(long[][] a, long B) {
		if (B == 1) {
			return a;
		}

		long[][] tmp = Pow(a, B / 2);

		if (B % 2 == 1) {
			return MatrixMul(MatrixMul(tmp, tmp), a);
		} else {
			return MatrixMul(tmp, tmp);
		}
	}

이런식으로 코드를 짤 수 있고, 분할 정복 단계에서 거듭제곱은 많이 다뤘기 때문에 이해는데 어렵지 않을 것이다.

 

※입력이 1000보다 클 수 있다.

따라서 먼저 remainder를 실행하고 계산을 진행 하는 것이 좋다.

		remainder(A);