[Java] 백준 / 행렬 제곱 / 10830번

[Java] 백준 / 행렬 제곱 / 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이다.

3 3
1 2 3
4 5 6
7 8 9

출력

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

468 576 684
62 305 548
656 34 412

접근 방식

1. 제곱의 수가 최대 1조이기 때문에 O(logN)으로 풀어야 한다
2. 행렬 a와 b를 곱하는 함수를 구현한다
3. 분할정복으로 행렬의 B제곱을 logB로 구현한다

코드

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

public class Main_G4_10830 {

	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());
		
		
		long[][] 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] = Integer.parseInt(st.nextToken());
			}
		}
		
		long[][] answer = divideCal(matrix,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.setLength(sb.length()-1);
			sb.append("\n");
		}
		System.out.println(sb);
	}
	
	
	public static long[][] divideCal(long[][] x, long b ) {

		if(b == 1) {
			for(int i=0;i<x.length;i++) {
				for(int j=0;j<x.length;j++) {
					x[i][j] = x[i][j] % 1000;
				}
			}
			return x;
		}
		
		long[][] y = divideCal(x,b/2);
		return (b%2==0)? calProduct(y,y) : calProduct(calProduct(y,y),x);
	}
	
	public static long[][] calProduct(long[][] m1, long[][] m2) {
		int size = m1.length;
		
		long temp[][] = new long[size][size];
		
		for(int i=0;i<size;i++) {
			for(int j=0;j<size;j++) {
				int sum = 0;
				for(int k=0;k<size;k++) {
					sum += m1[i][k]*m2[k][j];
				}
				temp[i][j] = sum % 1000;
			}
		}
		
		return temp;
	}
	

}