[JAVA] BOJ11049 행렬 곱셈 순서

알고리즘 분류

• 다이나믹 프로그래밍

문제 풀이 방법

• 점화식의 특성에 따라, N이 주어졌을 때, N-1개 까지의 개수는 구할 수 있다고 가정
• D[i][j]: i부터 j까지 행렬의 연산 횟수
  • D[1][N] = D[1][j] + D[j + 1][N] + a, a = (j번째 행렬의 행의 개수) * (j + 1번째 행렬의 행의 개수) * (j + 1번째 행렬의 열의 개수)

코드

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

public class BOJ11049 {
    /*
    행렬 곱셈 순서
     */
    static class Matrix {
        int r, c;

        public Matrix(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N, dp[][];
    static Matrix matrix[];

    public static void main(String[] args) throws Exception {
        N = Integer.parseInt(br.readLine());

        matrix = new Matrix[N + 1];
        dp = new int[N + 1][N + 1];

        for(int i = 0; i < dp.length; i++) Arrays.fill(dp[i], -1);

        for(int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            matrix[i] = new Matrix(r, c);
        }

        System.out.println(func(1, N));
    }

    private static int func(int start, int end) {
        int result = Integer.MAX_VALUE;
        if(dp[start][end] != -1) return dp[start][end];
        if(start == end) return 0;
        if(start + 1 == end) {
            int tmp = matrix[start].r * matrix[end].r * matrix[end].c;
            return tmp;
        }

        for(int i = start; i< end; i++) {
            result = Math.min(result, func(start, i) + func(i + 1, end) + (matrix[start].r * matrix[i].c * matrix[end].c));
        }

        return dp[start][end] = result;
    }
}

느낀점

• 스스로 문제해결을 하려고 했는데, 어려워서 책을 참고하여 풀었다. 점화식의 기본적인 성질을 사용해서 문제를 풀이하는 것이 이해가 안되는 듯, 되는 듯, 어려운 듯, 안어려운 듯,,,
• 풀이가 이해는 되지만, 만약, 코테에서 이런 문제가 나왔을 때, 이렇게 풀 수 있을 지 모르겠다,,
  (혼자만의 힘으로 풀 수 있을 때까지 연습해야지!)
• 다른 사람의 풀이도 봤는데, 3중 반복문와 DP를 사용하여 문제를 풀 수 있는 것 같다. 나중에 꼭 다시 풀어봐야겠다.