[백준] 11049 행렬 곱셈 순서 - DP + 재귀 + 수학 JAVA

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

11049번: 행렬 곱셈 순서

코드설명

DP와 수학 문제입니다.

 

행렬의 곱셈 공식인 NxM 행렬과 MxK 행렬이 있으면 해당 행렬을 곱할시 NxK 행렬이 된다는점을 알아야합니다.

 

simulate(int start, int end)함수에 대해 설명해보면,

1. 행렬이 1개인 경우, start == end일 때, 곱셈이 필요 없으므로 0을 반환합니다. 1개의 행렬이므로 곱셈을 진행하지않습니다.
2. 행렬이 2개인 경우, start + 1 == end일 때, 두 행렬을 곱셈한 결과를 반환합니다. 바로 인접한 행렬을 곱하는 경우이기 때문에 그렇습니다.

3. 행렬이 3개 이상인 경우, for 루프를 통해 가능한 모든 분할 지점을 검토하고, 각각의 경우에 대해 최소 곱셈 횟수를 계산합니다.

 

위와 같이 재귀를 활용하면서 만약에 ABCDE 행렬에서 ABCD * E 가 주어졌다고 가정해봅니다. 그렇다면 ((ABC)D) -> ((AB)C)D)E) 이런식으로 변하게 됩니다. 최적의 해를 찾기 위해 A(BC)D*E 이 경우도 검사합니다.

코드

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

public class Main {
	
	public static int N, M, K;
	public static int answer;
	public static int[][] arr;
	public static int[][] dp;
	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());
    	arr = new int[501][2];
    	dp = new int[501][501];
    	for(int i=0;i<501;i++) {
    		Arrays.fill(dp[i], -1);
    	}
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<2;j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	answer = simulate(0, N-1); //첫번째 행렬부터 마지막 행렬까지 모두 곱했을때, 하나로 합쳤을때 드는 최소값을 나오게 합니다.
    	System.out.println(answer);
	}
	
	public static int simulate(int start, int end) {
		if(dp[start][end]>=0) return dp[start][end];
		if(start == end) return 0;
		int result = Integer.MAX_VALUE;
		
		for(int i=start; i< end; i++) {
			result = Math.min(result, simulate(start, i) + simulate(i+1, end) + arr[start][0] * arr[i][1] * arr[end][1]);
		}
		return dp[start][end] = result;
	}
}