[백준] 10830 행렬 제곱 <Java>

문제

---

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

 

 

풀이

---

분할정복을 통해서 풀이를 하면 되는 문제다.

 

시간을 줄이기 위해서

A^4 = A * A * A * A 로 푸는 것이 아니라

A^4 = A^2 * A^2 의 방식으로 문제를 풀었다.

 

이때 문제가 되는것은 지수가 홀 수 일 경우다.

A^5 = A^4 * A 와 같이 짝수의 거듭제곱에 기존의 A를 한번더 곱해주는 방식으로 구현을 하였다.

 

분할정복의 풀이에 맞게 재귀로 나눠주면서 가장 마지막에 도착했을 때 값을 곱해서 나아가는 방식으로 풀면된다.

기존의 합병정렬의 방식을 생각하면 편하다.

 

우선 위의 방식의 코드를 보여주면

static long[][] pow(long[][] A, long exp){
	if(exp == 1) {
		return A;
	}
	
	long[][] res = pow(A, exp/2);
	
	res = multiply(res, res);		
	if(exp % 2 == 1L) {
		res = multiply(res, procession);
	}
	
	return res;
}

위와 같이 exp 지수가 1이 될 때까지 반복하면 된다.

이 때, 홀수 일경우에는 procession 이라는 처음 입력받은 행렬을 곱해주면서 A^exp * A 를 완성 시켜준다.

 

행렬의 곱은 3중 반복문으로 구현하였고, 아래와 같다.

static long[][] multiply(long[][] pro1, long[][] pro2){
	
	long[][] res = new long[n][n];
	
	for(int k = 0 ; k < n ; k++) {
		for(int i = 0 ; i < n ; i++) {
			for(int j = 0 ; j < n ; j++) {
				res[i][j] += pro1[i][k] * pro2[k][j];
				res[i][j] %= 1000;
			}
		}
	}
	
	return res;
}

문제에서 원하는 결과는 MOD(1000)이기 때문에 값을 계속해서 모듈러 1000의 값을 넣어 주었다.

이와 같이 위의 두가지 함수를 이용해서 풀 수 있다.

 

<전체코드>

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

public class Main {	

	static StringBuilder sb = new StringBuilder();
	static int n;
	static long exp;
	static long[][] procession; 
	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());
		exp = Long.parseLong(st.nextToken());
		
		procession = new long[n][n];
		long[][] A = new long[n][n];
		for(int i = 0 ; i < n ; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0 ; j < n ; j++) {
				procession[i][j] = Long.parseLong(st.nextToken());
				A[i][j] = procession[i][j];
			}
		}
		
		long[][] result = pow(A, exp);		
		for(int i = 0 ; i < n ; i++) {
			for(int j = 0 ; j < n ; j++) {
				sb.append(result[i][j] % 1000 + " ");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
	
	static long[][] pow(long[][] A, long exp){
		if(exp == 1) {
			return A;
		}
		
		long[][] res = pow(A, exp/2);
		
		res = multiply(res, res);		
		if(exp % 2 == 1L) {
			res = multiply(res, procession);
		}
		
		return res;
	}
	
	static long[][] multiply(long[][] pro1, long[][] pro2){
		
		long[][] res = new long[n][n];
		
		for(int k = 0 ; k < n ; k++) {
			for(int i = 0 ; i < n ; i++) {
				for(int j = 0 ; j < n ; j++) {
					res[i][j] += pro1[i][k] * pro2[k][j];
					res[i][j] %= 1000;
				}
			}
		}
		
		return res;
	}
}