[BOJ] 11049번: 행렬 곱셈 순서

 

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

11049번: 행렬 곱셈 순서

 

 

알고리즘 분류: 다이내믹 프로그래밍

public class Main {
    static Myscanner sc = new Myscanner();
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static final int inf = 987654321;
    public static void main(String[] args) {
        int N =sc.nextInt();
        int d[] = new int[501];
        int[][] dp = new int[501][501];
        
        d[0] = sc.nextInt();
        d[1] = sc.nextInt();
        
        for(int n = 1; n<N-1;n++){
            d[n]=sc.nextInt();
            d[n+1] = sc.nextInt();
        }
        d[N-1]=sc.nextInt();
        d[N]= sc.nextInt();
        
        for(int dia = 0; dia<N;dia++)
        {
            for(int n=1;n<=N-dia;n++){
                int m = n+dia;
                
                if(n==m){
                    dp[n][m]=0;
                    continue;
                }
                
                dp[n][m]=inf;
                for(int k=n;k<m;k++){
                    dp[n][m] = Math.min(dp[n][m], dp[n][k]+dp[k+1][m]+d[n-1]*d[k]*d[m]);
                }
            }
        }
        System.out.println(dp[1][N]);
    }
}

 

다이내믹 프로그래밍 문제이다.

 

학교에서 알고리즘에 대해 배울 때 나왔던 문제 중 이것과 비슷한 문제가 "연쇄 행렬 최소 곱셈" 문제..

사실 완전히 이해 하지 못하고 다른 사람들의 코드를 참조하여 풀었다..

다시 공부가 필요한 시점 dp는 너무 어려움..