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

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

11049번: 행렬 곱셈 순서

 

입출력이 참 힘든 자바로 넘어와서 문제를 풀었다.

처음에 문제보고 어떻게 풀지 고민하다가 답도 없어서 알고리즘 분류를 살짝 봤더니 dp 였다. dp 인 거를 알고 나서 보니까 좀 고민하다가 풀었는데 문제를 보고 어떤 유형인지 알아내는 거를 잘 해야겠다. 풀고나서 보니 매우 유명한 dp 문제인 것 같다. 문제 좀 더 풀어야겠다.

 

dp 문제이니까 우선 점화식을 생각해보자.

 

d[L][R] 을 L 번째 부터 R 번째 까지의 행렬을 곱하는 필요한 최소 연산 횟수라고 잡아보자.

 

그러면 다음과 같이 문제를 쪼갤 수 있다.

d[L][R] = min ( d[L][K] + d[K+1][R] + C(k,k+1) )  (L <= K < R ) 

여기서 C(k,k+1) 은 (L~K) 까지 곱한 거랑 (K+1 ~R) 곱한 거를 곱하는 연산 횟수이다. 

 

이 점화식을 가지고 처음에 d[0][1] d[1][2] d[2][3] ... 을 넣어준 다음

d[0][2] d[1][3] d[2][4] 넣고 d[0][3] d[1][4] 이런 식으로 범위를 증가시키면서 넣어주는 식으로 하면 된다. 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int[] r = new int[501];
		int[] c = new int[501];
		int[][] d = new int[501][501];

		String[] str = br.readLine().split(" ");

		int n = Integer.parseInt(str[0]);

		for (int i = 0; i < n; i++) {
			str = br.readLine().split(" ");
			r[i] = Integer.parseInt(str[0]);
			c[i] = Integer.parseInt(str[1]);
		}

		for (int i = 0; i < n - 1; i++) {
			d[i][i + 1] = r[i] * c[i] * c[i + 1];
		}

		for (int i = 2; i < n; i++) {
			for (int j = 0; j + i < n; j++) {
				int temp = Integer.MAX_VALUE;
				for (int k = j; k < j + i; k++) {
					if (temp > d[j][k] + d[k + 1][j + i] + r[j] * r[k + 1] * c[j + i]) {
						temp = d[j][k] + d[k + 1][j + i] + r[j] * r[k + 1] * c[j + i];
					}
				}
				d[j][j + i] = temp;
			}
		}

		bw.write(d[0][n - 1] + "");
		bw.close();
	}

}