[BOJ-10830][분할정복] 행렬 제곱 -Java

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

10830번: 행렬 제곱

package algo;

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

public class boj_10830_행렬제곱 {
	static int N;
	static long M, useMap[][], map[][];
	static List<Long> list = new ArrayList<>();
	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());
		M=Long.parseLong(st.nextToken());
	
		map = new long[N][N];
		useMap=new long[N][N];
		
		for(int i=0; i<N; i++) {
			st= new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				map[i][j]=Long.parseLong(st.nextToken())%1000;
				useMap[i][j]=map[i][j];
			}
		}
	
		long m=M;
		while(m>1) {
			list.add(m);
			m/=2;
		}
		solve( 1, list.size()-1);
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				System.out.print(useMap[i][j]+" ");
			}
			System.out.println();
		}
	}
	
	private static void solve(long m, int size) {
		if(size==-1) return;
		
		if(m*2==list.get(size)) {//그냥 곱해서  solve호출
			useMap=matrixMul(useMap,useMap);
			solve(m*2, size-1);
		}
		else { //곱하고 원래 배열 한번 더 곱해서 넘겨야함 
			useMap=matrixMul(useMap,useMap);
			useMap=matrixMul(useMap, map);
			solve(m*2+1, size-1);
		}
	}
	private static long[][] matrixMul(long[][] map1, long[][] map2) { 
		long tmpMap[][]=new long[N][N];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				long sum=0;
				for(int k=0; k<N; k++) {
					sum+=map1[i][k]*map2[k][j]%1000;
				}
				tmpMap[i][j]=sum%1000;
			}
		}
		return tmpMap;
	}

}

 

소요시간 : 1시간 1분

 

행렬의 거듭제곱을 하는 방법은 진짜 하나하나 곱해서 올라가는 방법도 있지만

 

2^1 * 2^1 = 2^2

2^2 * 2^2 = 2^4

2^4 * 2^4=  2^8

2^8 * 2^8 = 2^16

 

이런식으로 올라가는 방법이 있습니다.

그럼 만약 A의 10거듭제곱은 어떻게 구할 수 있을까요

 

A^1 * A^1 = A^2

A^2 * A^2 * A^1= A^5

A^5 * A^5 = A^10 처럼 구할 수 있습니다.

 

제가 푼 로직은 아래 코드를 통해서 미리 내가 구해야할 지수를 구해놓습니다.

 

그리고 dfs를 통해서 거듭제곱을 구합니다!

useMap은 현재 거듭제곱을 계속해서 구해가고 있는 행렬이고

그냥 map은 처음 입력받은 행렬입니다.

 

map이 필요한 이유는

A^2 * A^2 * A^1= A^5   -> 이러한 케이스에서 A^1를 곱해줘야 하기 때문입니다!

끝~