[BOJ][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)
항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

 

출력

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

 

예제 입력

3
5 3
3 2
2 6

 

예제 출력

90

 

제한

시간 제한: 1초

메모리 제한: 256MB

 

---

풀이

특정 구간에서의 행렬 곱셈 최소 연산 횟수를 dp 배열로 저장한 후에 재사용하여 풀 수 있다.

 

어떤 구간 [i, j]에서의 최소 연산 횟수를 dp[i][j]라고 정의 하면 이는 다음과 같은 점화식으로 작성할 수 있다.

 

 

위 점화식의 의미는 다음과 같다.

 

구간 [i, j]의 최소 연산 횟수는 구간 [i, k]의 행렬을 곱했을 때 최소 연산 + 구간 [k+1, j]의 행렬을 곱했을 때의 최소 연산 + 두 구간의 행렬곱이다.

예를 들어, 행렬이 5개 (A1, A2, A3, A4, A5) 있다고 해보자.

 

이때 최소 연산 횟수를 구하려면 A1~A5까지의 행렬 곱을 구해야 하고

이는 A1 * (A2~A5), (A1~A2) * (A3~A5), (A1~A3) * (A4~A5), (A1~A4) * A5 중의 가장 최소 값을 고르는 것과 같다.

 

이때 파란색으로 표시한 왼족 값이 dp[i][k]에 해당하며

빨간색으로 표시한 오른쪽 값이 dp[k+1][j]에 해당하고

두 행렬을 곱하는 것이 d[i-1]*d[k]*d[j]에 해당한다.

 

이때 이전 값을 구하기 위해서 대각선 방향으로 dp값을 찾아간다.

 

정답

코드에서는 d 배열 대신 pair 형태로 값을 받아서 처리하도록 구현했다.

#include <iostream>
#include <string.h>
#include <string>
#include <deque>
#include <algorithm>
#include <vector>
#include <stack>
#include <cmath>
#include <map>
#include <queue>
using namespace std;
using ll = long long;
ll n;
int dp[501][501]; // dp[i][j] = A_i ~ A_j 까지의 행렬 곱의 최소 연산 횟수

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    vector<pair<int,int>> m;
    for (int i = 0; i < n; i++) {
        int r, c;
        cin >> r >> c;
        m.push_back({ r,c });
    }
    for (int i = 1; i <= n; i++) {
        dp[i][i] = 0;
    }
    for (int dia = 1; dia <= n - 1; dia++) {
        for (int i = 1; i <= n - dia; i++) {
            int j = i + dia;
            dp[i][j] = dp[i][i] + dp[i + 1][j] + m[i - 1].first * m[i].first * m[j-1].second;
            for (int k = i+1; k < j; k++) {
                int tmp = dp[i][k] + dp[k + 1][j] + m[i - 1].first * m[k].first * m[j - 1].second;
                if (tmp < dp[i][j]) {
                    dp[i][j] = tmp;
                }
            }
        }
    }
    cout << dp[1][n];
    return 0;
}

---

이렇게 해서 백준 11049번 행렬 곱셈 순서 문제를 풀어보았습니다.

 

댓글로 질문을 남기시면 성실히 답해드리겠습니다

 

감사합니다.