백준 11049번 - 행렬 곱셈 순서(C++)

문제

크기가 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

문제 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 1e9;
int N;
vector<pair<int, int>> matrix;
vector<vector<int>> dp;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N;
    matrix.resize(N + 1);
    dp.assign(N + 1, vector<int>(N + 1, INF));
    
    for (int i = 1; i <= N; i++) {
        cin >> matrix[i].first >> matrix[i].second;
        dp[i][i] = 0;
    }
    
    for (int len = 2; len <= N; len++) {
        for (int i = 1; i <= N - len + 1; i++) {
            int j = i + len - 1;
            for (int k = i; k < j; k++) 
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + matrix[i].first * matrix[k].second * matrix[j].second);
        }
    }
    cout << dp[1][N] << "\n";
    
    return 0;
}

아이디어 

동적 기법을 이용했다. ABC라는 행렬 곱을 해야할 때, (AB)C로 AB를 먼저 곱할 수도있고 A(BC)로 BC를 먼저 곱할 수도 있다. 

예를 들면,

3
5 3
3 2
2 6

1. matrix배열에 행렬의 크기 값을 받는다.

2. DP[i][j]라고 했을 때, i와 j의 차이가 1일 때부터 N-1 때까지 배열을 계산한다. 

3. 중간 값을 통해 두개의 그룹으로 나눠서 최솟값을 구한다. 

4. Dp[1][N]의 값을 출력한다.