백준 11049 행렬 곱셈 순서 Java

 

동적 프로그래밍에서 유명한 문제인 행렬 곱셈 순서 문제이다.

 

2018년도에 알고리즘 수업을 들으면서 한 번 봤던 문제인데

이번에 제대로 이해하려고 노력해보니까

정말 헷갈리고 어려웠다..

 

행렬 곱셈은 A행렬과 B행렬을 곱하면

A의 행의수 * A의 열의 수 * B의 열의 수 를 곱하면 행렬 곱셈 횟수가 나오게 된다.

 

dp[i][j]에는 i번과 j번의 곱셈 횟수가 저장된다.

예제처럼 3개의 행렬의 곱셈 횟수를 구하는 과정을 보면

0번째 행렬과 1번째 행렬의 곱셈 횟수가 dp[0][1]에 저장되고

1번째 행렬과 2번째 행렬의 곱셈횟수가 dp[1][2]에 저장되고

0번째 행렬과 dp[1][2]와 곱해서 dp[0][2]에 저장되고

2번째 행렬과 dp[0][1]과 곱해서

전에 저장했던 dp[0][2]와 더 작은 값을 비교해서 dp[0][2]에 저장된다.

 

이러한 과정을 거쳐서 행렬 곱셈의 최소 횟수를 출력할 수 있다.

반복문으로 구현하는 방법과 재귀 호출로 구현하는 방법이 있는데

 

나는 재귀호출로 구현하는 방법이 코드가 훨씬 더 이해가 잘되는 것 같았다.

실행 과정을 알아도 반복문의 변수들을 어떻게, 왜 그렇게 짠 건지 이해가 잘 안 된다..

반복문으로 구현하는 방법을 누군가 자세하고 친절히 설명해주면 좋겠다.

검색을 많이 해봤지만 이해가 잘되는 글이 없었다ㅠ

실행 속도는 반복문이 더 빠르다.

 

재귀 호출로 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Q11049 {
    static int [][] a;
    static int [][] dp;
    
    public static int solve( int start, int end) {
        if(start == end) return 0;
        if(dp[start][end]!= Integer.MAX_VALUE) {
            return dp[start][end];
        }
        for(int i=start; i<end; i++) {
            int cost = solve(start, i)+solve(i+1, end)+ a[start][0] * a[i][1] * a[end][1];
            dp[start][end] = Math.min(dp[start][end], cost);
        }
        return dp[start][end];
    }
    
    public static void main(String [] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        a = new int[n][2];
        dp = new int[n][n];
        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(reader.readLine());
            a[i][0] = Integer.parseInt(st.nextToken());
            a[i][1] = Integer.parseInt(st.nextToken());
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
 
        System.out.println(solve(0, n-1));
    }
}

 

반복문으로 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Q11049_ver2 {
    public static void main(String [] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int [][] a = new int[n][2];
        int [][] dp = new int[n][n];
        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(reader.readLine());
            a[i][0] = Integer.parseInt(st.nextToken());
            a[i][1] = Integer.parseInt(st.nextToken());
        }
        
        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=0; k<i; k++) {
                    int cost = dp[j][j+k] + dp[j+k+1][j+i] + a[j][0] * a[j+k][1] * a[j+i][1];
                    dp[j][j+i] = Math.min(dp[j][j+i], cost);
                }
            }
        }
        System.out.println(dp[0][n-1]);
    }
}