[BOJ 10830번] 행렬 제곱

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

10830번: 행렬 제곱

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

public class Main {
	
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	static int N;
	static long B;
	static int[][] matrix1;
	
	public static void main(String args[]) throws Exception {
		String[] str=br.readLine().split(" ");
		N=Integer.parseInt(str[0]);
		B=Long.parseLong(str[1]);
		matrix1=new int[N][N];
		for(int i=0;i<N;i++) {
			String s[]=br.readLine().split(" ");
			for(int j=0;j<N;j++) {
				matrix1[i][j]=Integer.parseInt(s[j]);
			}
		}
		int[][] matrixFinal=matrixResult(B);
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				bw.write(matrixFinal[i][j]%1000+" ");
			}
			bw.write("\n");
		}
		bw.flush();
		bw.close();
	}
/*	
	static int[][] matrixMultiply(int[][] matrixA, int[][] matrixB) {
		int matrixResult[][]=new int[N][N];
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				for(int l=0;l<N;l++) {
					matrixResult[i][j]+=matrixA[i][l]*matrixB[l][j];
				}
				matrixResult[i][j]%=1000;
			}
		}
		return matrixResult;
	}
*/	
	static int[][] matrixResult(long num){
		int[][] temp=new int[N][N];
		int[][] result=new int[N][N];
		if(num==1) return matrix1;
		if(num%2==0) {
			temp=matrixResult(num/2);
			for(int i=0;i<N;i++) {
				for(int j=0;j<N;j++) {
					for(int l=0;l<N;l++) {
						result[i][j]+=temp[i][l]*temp[l][j];
					}
					result[i][j]%=1000;
				}
			}
			return result;
		}
		else {
			temp=matrixResult(num-1);
			for(int i=0;i<N;i++) {
				for(int j=0;j<N;j++) {
					for(int l=0;l<N;l++) {
						result[i][j]+=temp[i][l]*matrix1[l][j];
					}
					result[i][j]%=1000;
				}
			}
			return result;
		}
	}
}

 이 문제는 분할정복을 이용해서 풀어볼 것입니다.

행렬의 B제곱을 구하려고 할 때 3 가지 경우로 나누어서 살펴볼 것입니다.

1. B=1인 경우

주어진 행렬을 그대로 return하면 됩니다.

2. B가 짝수인 경우

리턴값은 (행렬의 B/2제곱)*(행렬의 B/2제곱)입니다.

3. B가 홀수인 경우

리턴값은 (행렬의 B-1제곱)*주어진 행렬 입니다.

이를 반복해서 구현한 것이 matrixResult 함수이고, 재귀를 이용해 이를 구현했습니다.