[BOJ] 11049: 행렬 곱셈 순서(JAVA)

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

11049번: 행렬 곱셈 순서

크기가 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보다 작거나 같다.

예제 입력 1 

3

5 3

3 2

2 6

예제 출력 1 

90

 

---

[문제 풀이]

DP를 이용해서 해결하는 문제이다.

dp[i][j]에 저장되는 값은 Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + dp[i][0] * dp[k][1] * dp[j][1])이다.

dp[i][j]는 i번째 행렬부터 j번째 행렬까지 곱할 때의 연산횟수가 저장된다. 

i번째 행렬과 j번째 행렬 사이의 행렬들의 곱의 연산 횟수 중 최솟값을 찾아 dp[i][j] 값을 업데이트하면 된다.

 

[코드]

import java.util.*;

public class Main{
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[][] matrix = new int[N][2];
		for(int i=0;i<N;i++) {
			matrix[i][0] = sc.nextInt();
			matrix[i][1] = sc.nextInt();
		}
		
		int[][] dp = new int[N][N];
		
		for(int i=1;i<N;i++) {
			for(int j=0;j<N-i;j++) {
				dp[j][j+i] = Integer.MAX_VALUE;
				for(int k=j;k<i+j;k++) {
					int cost = dp[j][k] + dp[k+1][j+i] + matrix[j][0] * matrix[k][1] * matrix[j+i][1];
					dp[j][j+i] = Math.min(dp[j][j+i], cost);
				}
			}
		}
		
		System.out.println(dp[0][N-1]);
	}
}