[백준] 11049번: 행렬 곱셈 순서

11049번: 행렬 곱셈 순서

문제

크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.

예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.

• AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.
• BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.

같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.

행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

입력

첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.

둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)

항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

출력

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.

예제 입력 1

3
5 3
3 2
2 6

예제 출력 1

90

 

이런 문제는 문제에 주어진 예제들을 곱씹어보는 것이 중요합니다. 행렬의 순서는 변하지 않고, 곱셈을 하는 순서를 어떻게 묶어가느냐가 중요한 문제입니다. 이 문제를 DP로 풀 것을 생각하고, 중간에 경유하게 되는 인덱스 i를 잘 생각해서, arr[st][0] * arr[i][1] * arr[ed][1] 을 만들어내는 것이 관건이라고 할 수 있을 것 같네요.

 

#include <iostream>
using namespace std;

int arr[501][2];
long long dp[501][501];

long long calculate(int st, int ed) {
    if (dp[st][ed] != -1) return dp[st][ed];
    if (st == ed) return dp[st][ed] = 0;
    if (ed - st == 1) {
        return dp[st][ed] = arr[st][0] * arr[st][1] * arr[ed][1];
    }

    for (int i = st; i < ed; i++) {
        long long tmp = calculate(st, i) + calculate(i + 1, ed) + arr[st][0] * arr[i][1] * arr[ed][1];

        if (dp[st][ed] == -1 || dp[st][ed] > tmp) {
            dp[st][ed] = tmp;
        }
    }

    return dp[st][ed];
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i][0] >> arr[i][1];
        for (int j = 1; j <= n; j++) {
            dp[i][j] = -1;
        }
    }

    cout << calculate(1, n) << '\n';
    return 0;
}