[백준][BOJ-10830][자바] 행렬 제곱

www.acmicpc.net/problem/10830

10830번: 행렬 제곱

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

public class Main {
	static HashMap<Long, int[][]> hm = new HashMap<>();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		long B = Long.parseLong(st.nextToken());
		int[][] matrix = new int[N][N];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 처음부터 1000이 넘게 들어오는 경우
		matrix = matrixMod(matrix);
		
		// A^1 과 A^2 저장
		hm.put((long) 1, matrix);
		multiplyMatrix(matrix, matrix,2);
		
		divideConquer(B);
		
		int[][] result = hm.get(B);
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				System.out.print(result[i][j]+" ");
			}
			System.out.println();
		}
	}
	
	public static void divideConquer(long cnt){
		if(hm.containsKey(cnt)) return;
		
		long first = 0;
		long second = cnt/2;
		
		if(cnt %2 == 0) first = cnt/2;
		else first = (cnt/2)+1;
		
		divideConquer(first);
		divideConquer(second);
		
		multiplyMatrix(hm.get(first), hm.get(second), cnt);
	}
	
	public static int[][] multiplyMatrix(int[][] a, int[][] b, long cnt){
		int[][] temp = new int[a.length][a.length];
		
        for(int i=0; i<a.length;i++){
            for(int j=0; j<b[0].length;j++){
                for(int k=0; k<a[0].length;k++){
                	temp[i][j] += a[i][k]*b[k][j];
                }
                 
            }
        }
        
        temp = matrixMod(temp);
        hm.put(cnt, temp);
        return temp;
        
	}
	
	public static int[][] matrixMod(int[][] matrix){
		for(int i=0; i<matrix.length; i++) {
			for(int j=0; j<matrix[0].length; j++) {
				matrix[i][j] %= 1000;
			}
		}
		return matrix;
	}
}

정리

• 처음부터 행렬A에 1000이 넘는 값이 들어올 수 있어서 처리를 해줘야 한다. ( 80프로에서 틀린다... )
• A^1과 A^2에 대한 값을 HashMap에 저장한다.
• 재귀를 통해 HashMap에 값이 있다면 더 이상 분할하지 않는다.
• multiplyMatrix()를 통해 곱하고 HashMap에 저장한다.
• 곱이 일어나는 매 순간마다 %1000을 해줘야한다.