[백준 C++] 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 출력 90

## 풀이
다이나믹 프로그래밍 문제이다. 행렬들을 나열하여 i번째부터 j번째까지의 곱셈 연산 횟수를 구하고 이를 반복하여 0번째부터 n-1번째 까지의 연산을 하면 된다. 행렬들의 길이가 작은것부터 구하면 되고, 행렬들이 i부터 j까지 있을때 그것을 중간의 k번째에서 2개의 행렬들로 나누어 dp로 구한 각각의 값들을 더하고 k부분에서 두행렬을 곱했을때의 값을 구하면 dp를 할 수 있다.(코드를 보면 이해하기 쉬울 것이다.)

## 어려웠던 점
처음에는 dp를 1차원으로 사용하여 약간 그리디스럽게 접근했다. 마지막까지의 최소치를 구하고 그위에 행렬이 추가되었을때 자신을 바로 앞과 곱하고 전체와 곱할것인지 아니면 전체와 바로 곱할것인지 하면서 풀었는데 그렇게 풀면 틀린다.

## 배운 점 / 느낀 점
dp는 항상 어려운것 같다. 2차원적으로 생각하는것을 계속 염두해두어야겠다.

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<pair<int,int>> a;
int dp[510][510];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    a = vector<pair<int,int>>(n, {0,0});
    for (int i = 0; i < n; i++) {
        int r, c;
        cin >> a[i].first >> a[i].second;
    }

    for (int i = 1; i < n; i++) { // i는 length
        for (int j = 0; j < n-i; j++) {
            for (int k = j+1; k <= j+i; k++) {
                if(dp[j][j+i] == 0) dp[j][j+i] = a[j].first*a[k].first*a[j+i].second+dp[j][k-1]+dp[k][j+i];
                dp[j][j+i] = min(dp[j][j+i], a[j].first*a[k].first*a[j+i].second+dp[j][k-1]+dp[k][j+i]);
            }
        }
    }

    cout << dp[0][n-1];
    return 0;
}