[알고리즘] Java / 백준 / 행렬 곱셈 순서 / 11049

[알고리즘] Java / 백준 / 행렬 곱셈 순서 / 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보다 작거나 같다.

접근 방식

행렬 개수가 n개일 때의 행렬 최소 연산을 cal(1,n)이라 하자.

cal(1,n)을 구하기 위해 1< k < n 인 k를 두면 cal(1,n) = cal(1,k) + cal(k+1,n) + (1의 행 값) (k의 열 값 혹은 k+1의 행 값) (n의 열 값) 이다.

이 때 반복되는 연산을 막기 위해 dp배열을 만들어 저장한다.

코드

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

public class Main_11049 {

	
	static int cal(int l, int r) {
		if(dp[l][r] != -1) return dp[l][r];
		else if(l == r) return 0;
		else {
			for(int i=l;i<r;i++) {
				int temp = cal(l,i)+cal(i+1,r)+matrix[l][0]*matrix[i][1]*matrix[r][1];
				if(dp[l][r] == -1 || temp < dp[l][r]) dp[l][r] = temp;
			}
			return dp[l][r];
		}
	}
	
	static int[][] dp;
	static int[][] matrix;
	static int n;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		matrix = new int[n][2];
		
		for(int i=0;i<n;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			matrix[i][0] = Integer.parseInt(st.nextToken());
			matrix[i][1] = Integer.parseInt(st.nextToken());
		}
		
		dp = new int[n][n];
		
		for(int i=0;i<n;i++) {
			Arrays.fill(dp[i], -1);
		}
		
		System.out.println(cal(0,n-1));
		
		
	}

}