[백준 10830] 행렬 제곱(Java)

https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱

문제

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

입력

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

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

출력

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

풀이 설명

1. 분할하지 않고 그냥 거듭제곱 다 곱해서 풀었더니 메모리 초과가 났다ㅠ.ㅠ

2. 제곱하는 수 B가 1이 될 때까지 2등분으로 분할해서 풀어야 통과가 된다. 

   ex) B=7이라면, n^7 -> (n^3 * n^3) * n^1 -> ((n^1 * n^1) * n^1) * ((n^1 * n^1) * n^1) * n^1

   ex) B=9라면, n^9 -> (n^4 * n^4) * n^1 -> (n^2 * n^2) * (n^2 * n^2) * n^1

                           -> ((n^1 * n^1) * (n^1 * n^1)) * ((n^1 * n^1) * (n^1 * n^1)) * n^1

3. 분할해서 곱하는 함수 multipleMatrix를 선언하고, 매개변수로 제곱수 B를 넘긴다.

  3-0. 만약 B가 1이 되었다면, matrix의 각 원소를 1000으로 나눈 나머지로 바꾸고 리턴한다.

  3-1. B가 1보다 크다면, B를 2등분해서 multipleMatrix를 재귀호출하고, int[][]형 리턴값을 temp에 저장한다.

  3-2. 받은 temp를 제곱해서(temp*temp) temp2에 저장한다.

  3-3. 만약 B가 홀수라면, 2등분하고 1개가 남았을테므로, temp2에 temp를 한 번 더 곱해주고 리턴한다.

  3-4. B가 짝수라면, 그냥 temp2를 그대로 리턴한다.

Java 코드

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

public class Main {
	static int N;
	static long[][] matrix;
	
	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());
		
		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 = multipleMatrix(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);
	}
	
	public static long[][] multipleMatrix(long B) {
		long[][] temp = new long[N][N];
		
		if(B == 1) { //B가 1이면 matrix % 1000 리턴
			for(int i=0; i<N; i++)
				for(int j=0; j<N; j++)
					temp[i][j] = matrix[i][j] % 1000;
			return temp;
		}
		
		temp = multipleMatrix(B / 2); //B가 2로 더 나누어지면 분할
		long[][] temp2 = new long[N][N]; //temp끼리 곱해서 저장할 배열 변수
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				for(int k=0; k<N; k++) {
					temp2[i][j] += temp[i][k] * temp[k][j];
				}
				temp2[i][j] %= 1000;
			}
		}
		
		if(B % 2 == 1) {
			//B % 2 가 1이라면 matrix를 한번 더 곱해야 함. 한번 더 곱해서 저장할 배열 변수
			long[][] temp3 = 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++) {
						temp3[i][j] += temp2[i][k] * matrix[k][j];
					}
					temp3[i][j] %= 1000;
				}
			}
			return temp3;
		}else {
			return temp2;
		}
	} //multipleMatrix

}