백준 11049번 - 행렬 곱셈 순서

🎯 Logic

행렬 N개를 차례로 곱할 때 곱하는 순서는 상관 없다면 시작 위치 s 부터 마지막 위치 e까지의 행렬 곱의 최솟값은 다음과 같다

DP[s][e]= min(DP[s][k]+DP[k+1][e]+A[s][0]×A[e][1]×A[k][1]) (s<=k<e 인 k의 모든 값 중에서)

특정 구간까지의 행렬 곱 최솟값이 저장되면서 최종적인 구간까지의 행렬 곱 최솟값을 구해야 하므로 동적 계획법을 사용해야 한다

처음 풀이

처음 풀이는 DP를 구할때 대각선으로 완성시켰다

import java.io.*;
import java.util.StringTokenizer;

// 동적 계획법 1 - 행렬 곱셈 순서
public class Main {
    static int N;
    static int[][] A;
    static int[][] DP;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N=Integer.parseInt(br.readLine());

        A=new int[N+1][2];
        for(int i=1; i<N+1; i++){
            st=new StringTokenizer(br.readLine());
            A[i][0]=Integer.parseInt(st.nextToken());
            A[i][1]=Integer.parseInt(st.nextToken());
        }

        // DP 생성
        DP=new int[N+1][N+1];
        for (int i=0 ; i<N+1; i++){
            for(int j=0; j<N+1; j++){
                if(i==j) DP[i][j]=0;
                else DP[i][j]=Integer.MAX_VALUE;
            }
        }

        // 대각선으로 채워주기
        for(int j=1; j<N+1; j++){
            int e=j;
            for(int i=1; i<N+2-j; i++){
                for(int k=i; k<e; k++){
                    // 여러 개의 값들 중에서 최소값 찾기
                    // Math.min은 2개만 비교 가능
                    DP[i][e]=Math.min(DP[i][e],DP[i][k]+DP[k+1][e]+A[i][0]*A[e][1]*A[k][1]);
                }
                e++;
                if(e==N+1) break;
            }
        }

        System.out.println(DP[1][N]);
    }
}

Refactoring

행렬의 아래에서 위로 차례로 올라가면 더 쉽게 코드를 구현가능 했다

import java.io.*;
import java.util.StringTokenizer;

// 동적 계획법 1 - 행렬 곱셈 순서
public class Main {
    static int N;
    static int[][] A;
    static int[][] DP;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N=Integer.parseInt(br.readLine());

        A=new int[N+1][2];
        for(int i=1; i<N+1; i++){
            st=new StringTokenizer(br.readLine());
            A[i][0]=Integer.parseInt(st.nextToken()); // Matrix 에서 행
            A[i][1]=Integer.parseInt(st.nextToken()); // Matrix 에서 열
        }

        // DP 생성
        // DP[i][j] -> i 부터 j 까지 행렬 곱 중 최솟값
        DP=new int[N+1][N+1];
        // 밑에서 부터 위로 채워주기
        for(int i=N-1; i>0; i--) {
            for (int j = i + 1; j < N + 1; j++) {
                DP[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    DP[i][j] = Math.min(DP[i][j], DP[i][k] + DP[k + 1][j] + A[i][0] * A[j][1] * A[k][1]);
                }
            }
        }

        System.out.println(DP[1][N]);
    }
}