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

11049번: 행렬 곱셈 순서 (acmicpc.net)

11049번: 행렬 곱셈 순서

 

풀이

알고리즘 파악

DP

 

처음부터 DP 냄새가 나서 알고리즘은 쉽게 파악했지만... 디테일 한 풀이에서 시간이 많이 걸린 문제

 

구현

 

1. 행렬의 곱셈 방식 파악하기

n*m 의 행렬과 m*k의 행렬의 곱셈식은 n*m*k이다. 즉, 

(ABC)(DEF) -> (A의 N) * (D의 N) * (F의 M)인 것이다. 

 

2. DP

ABCDEF의 모든 경우의 수는  -> (A)(BCDEF) , (AB)(CDEF) , (ABC)(DEF) , (ABCD)(EF), (ABCDE)(F)이다.

ABCDEF의 최솟값은 위의 모든 경우의 수 중 최솟값인데, 이는 부분 계산에도 해당된다.

즉 (ABC)의 최솟값이나 (DEF)의 최솟값도 동일한 로직으로 구할 수 있고, 이를 메모제이션 기법으로 저장한다.

단, (A) 나(F) 같은 하나의 행렬은 최솟값이 없기에 0을 return 한다.

 

2-1 점화식

다시 (ABC)(DEF)를 예시로 들어 보자면, 

(ABC)(DEF) = (ABC)와(DEF) 행렬의 곱셈 값 + (ABC)의 최솟값 + (DEF)의 최솟값이 된다.

begin = A , i+1 = D , end = F로 삼고 점화식으로 표현하면,

arr[begin][0]*arr[i+1][0]*arr[end][1] + Dp(begin,i) + Dp(i+1,end)

이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
	static int n;
	static int[][] arr;
	static int[][] d;
	static int end;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		arr = new int[n][2];
		d = new int[n][n]; //begin end
		end = n-1; //끝 인덱스
		for(int i=0; i<n; i++)
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}

        System.out.print(Dp(0,n-1));
	}
	
	static int Dp(int begin,int end)
	{
		int min=Integer.MAX_VALUE;

		if(begin==end) return 0; //끝
		if(d[begin][end]!=0) return d[begin][end];

		for(int i=begin; i<end; i++)
		{
			int value =calc_matrix(arr[begin][0],arr[i+1][0],arr[end][1]) +Dp(begin,i)+ Dp(i+1,end);
			min = Math.min(min,value);
		}
		
		return d[begin][end]= min;
	}
	
	static int calc_matrix(int n , int m, int k)
	{
		return n*m*k;
	}
}