BOJ 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 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 2^31-1보다 작거나 같다.

재정의와 추상화

DP 문제 중 파일 합치기 문제와 비슷하게 진행되는 문제이다. 이런 유형의 문제가 많이 있는 것 같으니 정확하게 공부해두자!

처음 N개의 행렬의 세로, 가로 길이를 입력받는다. 입력받은 N개의 행렬 정보는 Matrix 구조체 변수의 arr에 저장된다. 그 후, 우리는 행렬의 곱셈 연산의 수를 계산해야 한다. 우리는 dp라는 이름의 2차원 배열을 선언하여 첫 번째 인덱스부터 두 번째 인덱스까지의 행렬곱을 진행했을 때 그 연산의 수를 저장한다. (dp[i][j])

i번째 인덱스의 행렬과 j번째 인덱스의 행렬까지의 곱셈 연산의 수의 합은 아래와 같은 점화식으로 나타낼 수 있다.

// k는 i부터 j - 1까지의 범위를 가진다.
dp[i][j] = min(dp[i][k] + dp[k + 1][j] + arr[i].height * arr[k].width * arr[j].width)

코드 작성

#include <iostream>
#include <climits>
using namespace std;

typedef struct {
    int height, width;
} Matrix;

Matrix arr[500];
int dp[500][500];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i].height >> arr[i].width;
    }

    for (int i = 1; i < n; i++) {
        for (int j = 0; j + i < n; j++) {
            dp[j][j + i] = INT_MAX;
            for (int k = 0; k <= i - 1; k++) {
                dp[j][j + i] = min(dp[j][j + k] + dp[j + k + 1][j + i]
                        + arr[j].height * arr[j + k].width * arr[j + i].width, dp[j][j + i]);
            }
        }
    }

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