[BOJ] 11049 - 행렬 곱셈 순서

https://www.acmicpc.net/problem/11049

BOJ - 행렬 곱셈 순서

문제 유형: 다이나믹 프로그래밍

문제 난이도: Gold III

시간 제한: 1초

메모리 제한: 256MB

 

문제

크기가 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보다 작거나 같다.

 

풀이

dp[start][end] = 구간 [start, end]의 최소 연산횟수로 한다.

 

우선 start == end인 경우, 자기자신이므로 0이다. dp에 값이 들어온적 있다면 그걸 반환한다.

그게 아니라면, 두 행렬의 곱 꼴로 만들어서 최소를 구해봐야 한다.

[start, i]와 [i, end]둘을 곱하는데 필요한 값을 구한다. [start, i]까지의 값과 [i, end]까지의 값이 필요하고, 둘 자체를 곱하는 값고 구해야 한다. 둘 자체를 곱하는 값은 arr[start][0] * arr[i][1] * arr[end][1]이다.

이 세 값을 모두 더하여 [start, end]에서의 결과를 최소로 업데이트해준다.

최종적인 결과를 dp에 저장하고 반환한다.

 

즉, 우리는 dp[0][n-1]의 값을 출력해주면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int n;
vector<vector<int>> dp(501, vector<int>(501, -1));

int solve(int start, int end, vector<vector<int>> &arr) {
  if (start == end) {
    return 0;
  }
  if (dp[start][end] != -1) {
    return dp[start][end];
  }

  int res = INT_MAX;
  for (int i = start; i < end; ++i) {
    int leftCost = solve(start, i, arr);
    int rightCost = solve(i + 1, end, arr);
    int currCost = arr[start][0] * arr[i][1] * arr[end][1];
    res = min(res, leftCost + rightCost + currCost);
  }

  return dp[start][end] = res;
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  vector<vector<int>> arr(n, vector<int>(2));
  for (int i = 0; i < n; ++i) {
    cin >> arr[i][0] >> arr[i][1];
  }

  if (n == 1) {
    cout << "0\n";
  } else if (n == 2) {
    cout << arr[0][0] * arr[0][1] * arr[1][1];
  } else {
    cout << solve(0, n - 1, arr) << "\n";
  }

  return 0;
}