[백준] 10830 행렬 제곱 - 재귀 + 분할정복 JAVA

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

10830번: 행렬 제곱

코드설명

재귀와 분할정복을 활용하는 문제입니다.

 

이 문제

단순히 for문을 활용하여 곱셈을 진행할경우, B의 최대 크기는 1000억 이기 떄문에 시간복잡도가 O( N * N * N) *B ) 이 될 것이기에 시간초과가 날것입니다. 

 

그렇기에 분할정복을 통해 해당 과정들을 O( N^3 log (B) ) 로 줄일 수 있습니다. 여기서 N의 크기는 2<=N<=5 이므로 N의 시간초과는 걱정하지 않아도 됩니다.

 

처음에 시간초과가 나서 당황했었는데, 이유는 아래의 코드에서 powMatrix(A, exponent/2)를 같은 결과인데 2번 굳이 연산하고 있습니다. 

public static int[][] powMatrix(int[][] A, long exponent) {
    if(exponent == 1) return A;
    if(exponent % 2 == 1) return multiplyMatrix(powMatrix(A, exponent - 1), A);
    return multiplyMatrix(powMatrix(A, exponent / 2), powMatrix(A, exponent/2));
}

아래의 코드로 중복연산을 피합니다. 사실 이 코드에서는 부분 문제에서 중복문제들이 발견되기에 DP를 사용해도 가능하다만, 이 문제에서는 함수내에서 같은 함수를 실행하므로 함수내에서 한번만 연산되도록 처리할 수 있습니다.

public static int[][] powMatrix(int[][] A, long exponent) {
    if(exponent == 1) return A;
    if(exponent % 2 == 1) return multiplyMatrix(powMatrix(A, exponent - 1), A);
    int[][] half = powMatrix(A, exponent/2);
    return multiplyMatrix(half, half);
}

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {
	public static int N;
	public static long B;
	public static int[][] map;
	public static int[][] dp;
	public static int answer = 0;
	public static int MOD = 1000;
    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());
    	B = Long.parseLong(st.nextToken());
    	
    	map = new int[N][N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());	
    		for(int j=0;j<N;j++) {
    			//B가 1이라면 map이 바로 호출되는데, 이떄 만약 1000을 넘을경우 MOD값이 반영이 안되므로 입력시에 바로 % MOD 처리를합니다.
    			map[i][j] = Integer.parseInt(st.nextToken()) % MOD;
    		}
    	}
    	
    	int[][] answerMap = divideConquer(map, B);
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<N;j++) {
    			System.out.print(answerMap[i][j]+" ");
    		}
    		System.out.println();
    	}
    	
    }
    
    public static int[][] divideConquer(int[][] matrics, long exponential) {
    	
    	if(exponential == 1L) { //만약 지수가 1 이라면 해당 matrics 1 개를 내보냅니다.
    		return matrics;
    	}
    	
    	int[][] result = divideConquer(matrics, exponential / 2); //지수를 /2 로 하여 재귀호출(분할정복)합니다.
    	
    	int[][] newMatrics = MultiplyMatrix(result , result); //재귀호출에서 얻은 result 값을 제곱합니다. (이를 통해 연산을 줄입니다)
    	if(exponential % 2 == 1L) {
    		return MultiplyMatrix(newMatrics, map); //계산한 행렬이 홀수이니 map 값을 곱해줘서 홀수값으로 만들어줍니다.
    	}
    	else {
    		return newMatrics;
    	}
    	
    }
    
    public static int[][] MultiplyMatrix(int[][] matricsA, int[][] matricsB) {
    	int[][] newMatrics = new int[N][N];
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<N;j++) {
    			for(int k=0;k<N;k++) {
    				newMatrics[i][j] += matricsA[i][k] * matricsB[k][j];
    				newMatrics[i][j] %= MOD;
    			}
    		}
    	}
    	
    	return newMatrics;
    		
    }
    
}

 

코드 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M; 
	public static long B;
	public static int answer = 0;
	public static int[][] matrix;
	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());
		B = Long.parseLong(st.nextToken());
		
		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;
			}
		}
		
		int[][] answerMap = powMatrix(matrix, B);
	   	for(int i=0;i<N;i++) {
    		for(int j=0;j<N;j++) {
    			System.out.print(answerMap[i][j]+" ");
    		}
    		System.out.println();
    	}
	}
	
	public static int[][] powMatrix(int[][] A, long exponent) {
		if(exponent == 1) return A;
		if(exponent % 2 == 1) return multiplyMatrix(powMatrix(A, exponent - 1), A);
		int[][] half = powMatrix(A, exponent/2);
		return multiplyMatrix(half, half);
	}
	
	public static int[][] multiplyMatrix(int[][] matrixA, int[][] matrixB){
		int[][] newMatrics = new int[N][N];
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				for(int k=0;k<N;k++) {
					newMatrics[i][j] += matrixA[i][k] * matrixB[k][j];
					newMatrics[i][j] %= 1000;
				}
			}
		}
		return newMatrics;
	}
	
}