[백준 11049] 행렬 곱셈 순서 (JAVA)

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

11049번: 행렬 곱셈 순서

 

오랜만에 dp문제를 풀게 되어서인지 많이 헤맸다...ㅜㅠㅠ

간단해보이면서도 생각해내기 어려운 문제였다.

dp[0][n-1] 은 0~n-1까지의 행렬의 곱셈값을 넣은 것을 뜻한다.

 

포문을 돌면서 아래의 과정으로 계산을 한다. 

dp[i][i+k] = Math.min(dp[i][i+k], dp[i][j]+dp[j+1][i+k] + arr[i][0]*arr[j][1]*arr[i+k][1]);

-> i~i+k의 곱셈값 은

1) dp의 i~i+k의 곱셈값

2) dp의 i~j까지의 곱셈값+ dp의 j+1~i+k의 곱셈값 + (i행렬의 행 * j행렬의 열 * i+k행렬의 열)

둘 중 작은 값으로 dp의 i~i+k 값에 넣는다!!

 

 

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		int[][] dp = new int[N][N]; //dp[0][N-1] : 0~n-1까지의 곱셈
		int[][] arr = new int[N][2]; // arr[i][0] : 행 , arr[i][1]: 열 
        
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
        
		for(int k=1; k<N; k++) {
			for(int i=0; i+k<N; i++) {
				dp[i][i+k] = Integer.MAX_VALUE;
				for(int j=i; j<i+k; j++)
					dp[i][i+k] = Math.min(dp[i][i+k], dp[i][j]+dp[j+1][i+k] + arr[i][0]*arr[j][1]*arr[i+k][1]);
			}
		}
		System.out.println(dp[0][N-1]);
	}
}