[JAVA] 11049 행렬 곱셈 순서

오늘은 문제는 

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

11049번: 행렬 곱셈 순서

 

저번의 파일합치기와 매우매우 유사하여 금방 해결..할줄 알았는데, 이상한 곳에서 실수해서 쪼큼 걸렸습니다.

그래도 잘했다~

 

-나의 풀이-

 

저번 파일합치기와 유사한 점이 많이 보였습니다. (<https://hardworking-sloth.tistory.com/8>

 

1. 연속되는 두개만 곱셈을 수행가능하다. 

 

2. 최솟값을 구한다.

 

따라서 디피를 선택하여 문제를 해결했습니다. 파일합치기에는 두 파일 각각 만드는 비용과 두 파일을 합치는 비용의 합이 중요했다면, 여기서는 '행렬이 합쳐진 경우에는 어떻게 계산을 이어나갈까' 가 문제의 해결 포인트라고 생각합니다.

 

 행렬의 곱에 대해서 조금만 생각해보면 쉽게 규칙을 발견할 수 있습니다.

 

이 과정을 method cal(int s, int k, int e) 라고 했습니다.

이를 이용하여 점화식을 세우자면, 

dp(s, e) = i) if(s==e)  return 0

                                     ii) if(s+1==e) return s.h * s.r * e.r

     iii) Math.min(

                                 for(int k=s; k<e ; k++){

                                                          dp(s,k) + dp(k+1, e) + cal(s,k,e) }

 

역시 시간을 단축하기위해서는 memoziation을 이용하여야 합니다. 

memo[i] [j] 라는 2차원 배열에 i~j까지 합치는데 최소비용을 저장하여 이용하였습니다.

 

-코드-

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

class matrix{
	int h;
	int r;
	public matrix (int h, int r) {
		this.h = h;
		this.r = r; 
	}
	}
public class Num11049 {
	static int n;
	static matrix[] input;
	static int memo[][];
	public static int dp(int s, int e) {
		if(s==e) {
			return memo[s][e] =0;
		}
		if(s+1==e) {
			return memo[s][e] = input[s].h*input[s].r*input[e].r;
		}
		if(memo[s][e]!= Integer.MAX_VALUE) {
			return memo[s][e];
		}
		for(int k=s;k<e;k++) {
			memo[s][e] = Math.min(memo[s][e], dp(s,k)+dp(k+1,e)+cal(s,k,e));
		}
		return memo[s][e];
	}
	public static int cal(int s, int k, int e) {
		return input[s].h*input[k].r*input[e].r;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(bf.readLine());
		input = new matrix[n+1];
		for(int i=1; i<=n; i++) {
			String[] tmp = bf.readLine().split(" ");
			input[i] = new matrix(Integer.parseInt(tmp[0]),Integer.parseInt(tmp[1]));
		}
		memo = new int[n+1][n+1];
		for(int i=1;i<=n;i++) {
			Arrays.fill(memo[i], Integer.MAX_VALUE);
		}
		dp(1,n);
		System.out.println(memo[1][n]);
	}
	
}

 

-후기- 

1. 디피는 점화식이다.

2. 저 법칙이 이제는 좀 이해가 됐을지도

3. 민경하 교수님 보고계신가요