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

 

 

---

문제 링크

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

11049번: 행렬 곱셈 순서

---

문제 풀이

백준 11066 파일 합치기와 비슷한 문제였으나 행렬 곱셉을 어떻게 DP 배열로 처리할 지에 대해 파악하기 힘든 문제였다.

- 상향식(Bottom-Up)으로 풀 경우 시간 복잡도 O(N^2) 

- 하향식(Top-Down)으로 풀경우 O(N!) , memorization 기법 활용하여 시간 내에 풀이 가능

- 최대치는 Integer 범위

- 행렬 A (m x k) , B (k x n) 일때 A * B = m x n 행렬이 된다. 이때 연산횟수는 m * k * n 이다.

 

참고. 행렬의 곱셈 

https://mathbang.net/562#gsc.tab=0

행렬의 곱셈, 행렬의 거듭제곱

 

 

여태까지 DP 문제를 풀 경우 행 단위로 순차적으로 채워나가는 형태였다면, 해당 문제의 경우 DP 배열의 경우 사선 방향으로 채워지는 형태를 보임

 

입력으로 받은 행렬의 r, c값을 하나의 인덱스(객체)라고 생각했을 때 조합을 구하면 아래와 같이 나타난다.

 

DP[i][j] := i 번째 행렬과 j 번째 행렬의 연산 횟수의 최소값

점화식의 경우 아래와 같다

DP[i][j] = Math.min(DP[i][j], DP[i][k] + DP[k + 1][j] + (A[i][0] * A[k + 1][0] * A[j][1]) 

이때 k 는 i <= k < j 
DP[i][j] 에서 i == j인 경우 0 , 그외 초기 최대값 설정

 

 

len(길이) = 2인 경우 

i = 1 일 때 j = 2 , k = 1 ( 1 <= k < 2 )

DP[1][2] = Math.min(DP[1][2], DP[1][1] + DP[2][2] + (5 * 3 * 2))  = 0 + 0 + 30

 

i = 2 일 때 j = 3 , k = 2 ( 2 <= k < 3 )

DP[1][2] = Math.min(DP[1][2], DP[2][2] + DP[3][3] + (3 * 2 * 6)) = 0 + 0 + 36 

 

---

len(길이) = 3인 경우 

i = 1 일 때 j = 3, k = 1 ( 1 <= k < 3)

DP[1][3] = Math.min(DP[1][3], DP[1][1] + DP[2][3] + (5 * 3 * 6)) = 0 + 36 + 90 = 126

- DP[1][1] = 0 

- DP[2][3] 은 2번 행렬과 3번 행렬의 연산 횟수 

- 고로 (2번 * 3번) * 1번에 대한 행렬 연산 횟수 구해짐

 

i = 1 일 때 j = 3, k = 2 ( 1 <= k < 3)

DP[1][3] = Math.min(DP[1][3], DP[1][2] + DP[3][3] + (5 * 2 * 6)) = 30 + 0 + 60 = 90

- DP[1][2] 은 1번 행렬과 2번 행렬의 연산 횟수 

- DP[3][3] = 0

- 고로 (1번 * 2번) * 3번에 대한 행렬 연산 횟수 구해짐

 

 

---

제출 코드

(1) Bottom-Up방식

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static InputProcessor inputProcessor = new InputProcessor();

    static int N;
    static int[][] MATRIX;
    static int[][] DP;

    public static void main(String[] args) throws IOException {
        input();

        preprocess();
        bottomUp();
        sb.append(DP[1][N]);

        output();
    }


    private static void input() {
        N = inputProcessor.nextInt();

        MATRIX = new int[N + 1][2];
        for(int i = 1; i <= N; i++) {
            MATRIX[i][0] = inputProcessor.nextInt();
            MATRIX[i][1] = inputProcessor.nextInt();
        }
    }

    private static void preprocess() {
        DP = new int[N + 1][N + 1];
        for(int i = 1; i < N; i++) {
            DP[i][i] = 0;
            DP[i][i + 1] = MATRIX[i][0] * MATRIX[i][1] * MATRIX[i + 1][1];
        }
    }

    private static void bottomUp() {
        for(int len = 3; 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 value = DP[i][k] + DP[k + 1][j] + (MATRIX[i][0] * MATRIX[k][1] * MATRIX[j][1]);
                    DP[i][j] = Math.min(DP[i][j], value);
                }
            }
        }
    }

    private static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static class InputProcessor {
        BufferedReader br;
        StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String input = "";
            try {
                input = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return input;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
    
}

 

(2) Top-Down 방식

- DP 배열에서 방문하지 않았다는 의미로 Integer.MAX_VALUE 초기화

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static InputProcessor inputProcessor = new InputProcessor();

    static int N;
    static int[][] MATRIX;
    static int[][] DP;

    public static void main(String[] args) throws IOException {
        input();

        preprocess();

        sb.append(topDown(1, N));

        output();
    }


    private static void input() {
        N = inputProcessor.nextInt();

        MATRIX = new int[N + 1][2];
        for(int i = 1; i <= N; i++) {
            MATRIX[i][0] = inputProcessor.nextInt();
            MATRIX[i][1] = inputProcessor.nextInt();
        }
    }

    private static void preprocess() {
        DP = new int[N + 1][N + 1];
        for(int i = 1; i < N; i++) {
            Arrays.fill(DP[i], 1, N + 1, Integer.MAX_VALUE);

            DP[i][i] = 0;
            DP[i][i + 1] = MATRIX[i][0] * MATRIX[i][1] * MATRIX[i + 1][1];
        }
    }


    private static int topDown(int a, int b) {
        if(a == b) return DP[a][b];
        if(DP[a][b] != Integer.MAX_VALUE) return DP[a][b];

        for(int k = a; k < b; k++) {
            int value = topDown(a, k) + topDown(k + 1, b) + (MATRIX[a][0] * MATRIX[k][1] * MATRIX[b][1]);
            DP[a][b] = Math.min(DP[a][b], value);
        }

        return DP[a][b];
    }

    private static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static class InputProcessor {
        BufferedReader br;
        StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String input = "";
            try {
                input = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return input;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
    
}