백준 11049번 - 행렬 곱셈 순서

문제

백준 11049번 - 행렬 곱셈 순서

아이디어

• dp[s][e]를 s ~ e 구간의 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값이라 가정한다.
• 최종 구하려는 것은 dp[1][N]이라 할 수 있다.
• 예를 들어 행렬의 크기 N이 4라면 가능한 경우의 수는 다음과 같다.

1. dp[1][3] + dp[4][4] + a
2. dp[1][2] + dp[3][4] + a
3. dp[1][1] + dp[2][4] + a

• 여기서 a는 앞 두 행렬의 필요한 곱셈 연산 횟수를 뜻한다.
• 근데 만약에 dp[1][3]을 구하려면 또 dp[1][1] + dp[2][3] + a와 dp[1][2] + dp[3][3] + a 중 최솟값을 알아야 한다.
• 그래서 이 문제는 탑다운 방식으로 메모이제이션을 이용해 부분 문제들을 해결하여 전체 문제를 해결할 수 있다.
• 행렬이 1개인 경우(dp[n][n])은 연산 횟수가 0이다.
• 행렬이 2개인 경우(dp[n][n+1])의 연산 횟수는 공식을 따른다.(N x M x K)
• 행렬이 3개 이상인 경우부터는 여러 경우의 수를 살펴본다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N^2)

코드 구현

package Baekjoon.dp;

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

/**
 * <a href = "https://www.acmicpc.net/problem/11049">백준 11049번 - DP : 행렬 곱셈 순서</a>
 * <br>
 * <a href = "">velog</a>
 * @since 2024-07-30
 */
public class BJ_11049 {

    static Matrix[] matrices;
    static int[][] dp;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        matrices = new Matrix[n + 1];
        dp = new int[n + 1][n + 1];

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

            StringTokenizer st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            matrices[i] = new Matrix(r, c);
        }

        System.out.println(solve(1, n));
    }

    private static int solve(int s, int e) {
        int min = Integer.MAX_VALUE;

        if (dp[s][e] != -1) { //메모이제이션
            return dp[s][e];
        }
        if (s == e) { //행렬 1개
            return 0;
        }
        if (e - s == 1) { //행렬 2개
            return matrices[s].r * matrices[s].c * matrices[e].c;
        }

        //행렬 3개 이상
        for (int i = s; i < e; i++) {
            int temp = matrices[s].r * matrices[i].c * matrices[e].c;
            min = Math.min(min, solve(s, i) + solve(i + 1, e) + temp);
        }

        return dp[s][e] = min;
    }

    static class Matrix {
        int r, c;

        public Matrix(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}