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

문제

크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.

예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.

• AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.
• BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.

같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.

행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

입력

첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.

둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)

항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

출력

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.

 

---

문제 풀이 (DP)

 

이 문제는 DP로 풀 수 있는 문제이다. 

 

유명한 DP 문제라고 하는데 어렵긴 하다..

 

 

 

A~i번 , i번 ~ B번까지 곱하는 연산 수는 다음과 같다.

[A~i]번까지의 연산수 + [i+1번,B]번까지의 연산수 + A*i*B 

 

이를 점화식으로 표현하면 dp[start][i] + dp[i + 1][end] + map[start][0] * map[i][1] * map[end][1] 으로 정의된다.

 

 

 

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

public class BOJ_G3_11049_행렬곱셈순서 {

	static int N;
	static int r, c;
	static int[][] map;
	static int[][] dp;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][2];
		dp = new int[N][N];
		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			r = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			map[i][0] = r;
			map[i][1] = c;
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (i == j)
					dp[i][j] = 0;
				else
					dp[i][j] = Integer.MAX_VALUE;
			}
		}

		for (int c = 1; c < N; c++) {
			for (int i = 0; i + c < N; i++) {
				calcul(i, i + c);
			}
		}

		System.out.println(dp[0][N - 1]);
	}

	private static void calcul(int start, int end) {
		for (int i = start; i < end; i++) {
			// A*B => a*b b*b b*c
			int cost = dp[start][i] + dp[i + 1][end] + map[start][0] * map[i][1] * map[end][1];
			dp[start][end] = Math.min(dp[start][end], cost);
		}

	}

}