[백준 11049] 행렬 곱셈 순서 [Java]

문제

11049번: 행렬 곱셈 순서

11049번: 행렬 곱셈 순서

 

---

풀이

문제 요약

행렬 N개의 곱셈 순서를 적절히 정해, 곱셈 연산 수의 최소값을 구해야 한다.

아이디어

행렬 곱셈은 결합 순서에 따라 계산 비용이 달라진다.

따라서, 각 구간 [L, R]을 적절히 나누는 위치 t를 찾아 최소 비용을 계산해야 한다.

점화식은 다음과 같다.

dp[L][R]: L ~ R 구간의 최소 곱셈 비용

dp[L][R] = dp[L][t] + dp[t + 1][R] + (matrix[L][0] * matrix[t][1] * matrix[R][1])

행렬이 1개 일 때

행렬이 1개 일 때, 즉 L == R일 때는 연산을 하지 않으므로, dp[L][L] = 0이 된다.

        // Solve
        int[][] dp = new int[N][N];
        for (int i = 0; i < N; ++i) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
            dp[i][i] = 0;
        }

행렬이 2개 이상 일 때

L < R일 때, dp[L][R]은 중간 경계 t에 의해 (L, t), (t + 1, R) 구간의 행렬 곱과 같다.

이를 dp[L][t] + dp[t + 1][R] + (matrix[L][0] * matrix[t][1] * matrix[R][1])으로 나타낼 수 있다.

가장 작은 행렬 곱부터 모든 구간에 대한 계산을 해주자.

        for (int gap = 1; gap < N; ++gap) {
            for (int L = 0; L < N; ++L) {
                final int R = L + gap;
                if (R >= N) {
                    break;
                }
                for (int t = L; t < R; ++t) {
                    final int matrixMul = matrix[L][0] * matrix[t][1] * matrix[R][1];
                    dp[L][R] = Math.min(dp[L][R], dp[L][t] + dp[t + 1][R] + matrixMul);
                }
            }
        }

풀이시간

30분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/11049.java

problem-solving/baekjoon-online-judge/normal/11049.java at main · rogi-rogi/problem-solving