문제#

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

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

출력#

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

풀이 과정#

일단 이 문제의 문제 조건을 보았을 때 N은 500까지이고 시간 제한은 1초이니 시간복잡도는 약 $O(N^3)$까지 허용되는 것으로 파악했습니다.

그러고 나서는 백준 10844번 문제 ¹를 풀 때처럼 기본적으로 dp를 이용하면서 각 행렬의 행과 열을 dp 배열의 행 차원의 요소로 넣은 뒤에 (std::pair 이용) 각 위치에서 양 사이드로 퍼져나가면서 필요한 곱셈 연산 수의 최솟값을 구하는 알고리즘을 구상했습니다.

자료구조로는 pair<int, pair<int, int>> dp[]를 구상했습니다.

i번째 행과 j번째 열에서 점화식은 다음과 같습니다.

$dp[i][j]=min(dp[i - 1][j].first + dp[i - 1][j].second.first * dp[i - 1][j].second.second * dp[i - 1][j + 1].second.second,dp[i - 1][j + 1].first + dp[i - 1][j].second.first * dp[i - 1][j].second.second * dp[i - 1][j + 1].second.second)$

이 문제의 예제 입력에 대해서는 잘 나왔지만 다른 예제에 대해선 반례가 많이 나와 이 알고리즘은 포기했습니다.

이 알고리즘을 포기하고 나서는 내가 알고있는 지식의 바깥 범위의 문제인것 같아 챗봇에게 문제를 다 알려주지 말고 아주 약간의 힌트만 달라고 하였습니다.

그 결과 이 문제에서는 분할 정복을 써야 한다고 나왔고 저는 분할 정복에 대해 익숙하지 않고 잘 몰랐기에 분할 정복에 대해 코드를 보고 이해하기로 하였습니다.

그 후 다시 dp의 배열을 처음에 잠깐 상상만 했다가 구현이 힘들 것 같아 포기했던 i행 j열이 i번째부터 j번째까지를 의미하는 배열로 자료구조를 바꿔서 제작하였습니다.

중간에 원래라면 재귀와 메모이제이션을 이용하여 풀면 이렇게까지 복잡하게 안가도 됐겠지만 탑-다운 방식의 dp를 안쓴지 오래되어 생각해내지 못했습니다.

확실히 그래프 탐색이나 다른 유형에 비해 dp가 약한게 느껴지고 더 연습해야겠습니다.

코드#

# include <iostream>
# include <numeric>

using namespace std;

int N;
pair<int, int> matrix[500];
int dp[500][500];

int main()
{
    cin >> N;

    fill(*dp, *dp + 500 * 500, numeric_limits<int>::max());

    for (int i = 0; i < N; ++i)
    {
        cin >> matrix[i].first >> matrix[i].second;
        dp[i][i] = 0;
    }

    for (int i = 1; i < N; ++i)
        for (int j = 0; j < N - i; ++j)
        {
            int tmp = i + j;
            for (int k = j; k < tmp; ++k)
            {
                const int cost = dp[j][k] + dp[k + 1][tmp] + matrix[j].first * matrix[k].second * matrix[tmp].second;
                dp[j][tmp] = min(dp[j][tmp], cost);
            }
        }

    cout << dp[0][N - 1];
}