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

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

11049번: 행렬 곱셈 순서

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

public class Main_BOJ_11049 {
	static int N;
	static int[][] sizes;
	static int[][] dp;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		N=Integer.parseInt(br.readLine());
		sizes=new int[N+1][2];
		dp=new int[N+1][N+1];
		for (int i=1; i<=N; i++) {
			st=new StringTokenizer(br.readLine());
			sizes[i][0]=Integer.parseInt(st.nextToken());
			sizes[i][1]=Integer.parseInt(st.nextToken());
		}
		for (int len=2; len<=N; len++) {
			for (int i=1; i<=N-len+1; i++) {
				int j=i+(len-1);
				dp[i][j]=Integer.MAX_VALUE;
				for (int k=i; k<j; k++) {
					int a=sizes[i][0], b=sizes[k][1], c=sizes[j][1];
					int cnt=a*b*c;
					if (dp[i][j]>dp[i][k]+dp[k+1][j]+cnt) {
						dp[i][j]=dp[i][k]+dp[k+1][j]+cnt;
					}	
				}
			}
		}
		System.out.println(dp[1][N]);
	}

}

점화식을 유도하는 dp 문제.

주의할 점은 행렬의 크기를 저장하는 배열을 만들어 cnt 값을 구하는 것이다.

(i, k), (k+1, j)를 곱한다면 i의 행xk의 열xj의 열로 곱셈 횟수가 정해진다.