[백준] 11049번: 행렬 곱셈 순서 (C++)

문제 링크

11049번: 행렬 곱셈 순서

---

주말을 이용해서 이 문제를 풀기로 했는데... DP를 잘 못 하는 저로서는 좀 쉽지 않았습니다.

그래서 chatGPT에게 힌트를 물어보니 DP 구성 방법에 대한 힌트를 잘 설명해 줬고,

그것을 기반으로 문제를 풀 수 있었습니다. 제가 푼 방식을 필기해 둘 겸해서 블로그에 작성해봅니다.

풀이

DP 풀이를 하면 됩니다.

이 문제에서 정말 다행인 것은 항상 순서대로 곱셈을 할 수 있는 크기의 입력만 주어진다는 것입니다.

문제에서 주어진 예시에 따르면 A부터 C까지 구하기 위해서는 (AB)C와 A(BC)의 최솟값을 구해주면 됩니다.

저는 개인적으로 이 문제가 Top-Down 방식으로 푸는 것이 편해서 Top-Down 방식 DP로 풀었습니다.

하지만 아래에 chatGPT를 참고하여 코딩해본 Bottom-up 방식 코드도 있으니 마음에 드는 코드로 공부해보시면 될 것 같습니다!

예제로 주어졌던 ABC만으로는 설명이 부족할 것 같으니, ABCD로 그려보면서 설명해 보겠습니다.

ABCD의 트리 모형

mid는 주어진 행렬들을 어디에서 분할해서 계산할 것인가를 나타낸 수입니다.

위 트리에서 계산되는 부분들을 색으로 표시해 보겠습니다.

• 파란색 : 실질적으로 계산되는 부분
• 빨간색 : 메모이제이션에 의해 반환되는 부분
• 청록색 : 합쳐서 계산되는 부분

 

위 과정에 의해서 풀이를 하되, 중복되는 부분은 메모이제이션으로 해결하면 됩니다.

중간에 들어가는 식들은 모두 다음과 같이 표현되며,

\[  mat(mid)*mat(mid+1) = r[st]*c[mid]*c[en]\]

최종 DP 점화식은 다음과 같습니다.

\[d[st][en] = d[st][mid] + mat(mid)*mat(mid+1) + d[mid+1][en]\]

풀이코드

탑-다운 방식으로 풀이한 코드는 아래와 같습니다.

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

int n;
int r[501], c[501];
int dp[501][501];

int rec(int st, int en) {
  if (st == en) return dp[st][en] = 0;
  if (dp[st][en] != INT_MAX) return dp[st][en];

  for (int mid = st; mid < en; mid++) {
    int left = rec(st, mid);
    int root = r[st]*c[mid]*c[en];
    int right = rec(mid + 1, en);
    dp[st][en] = min(dp[st][en], left + root + right);
  }

  return dp[st][en];
}

void solve() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> r[i] >> c[i];
    fill(dp[i], dp[i] + n + 1, INT_MAX);
  }
  cout << rec(1, n);
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios_base::sync_with_stdio(false);
  cin.tie(0);
#endif
  solve();
  return 0;
}

아래는 바텀업 방식으로 풀이한 코드입니다(chatGPT 참고) 

void solve {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> r[i] >> c[i];

  // 행렬 체인 길이에 따라 초기화
  for (int len = 2; len <= n; len++) {
    for (int st = 1; st <= n - len + 1; st++) {
      int en = st + len - 1;
      dp[st][en] = INT_MAX;

      for (int rt = st; rt < en; rt++) {
        dp[st][en] = min(dp[st][en], dp[st][rt] + dp[rt+1][en] + r[st]*c[rt]*c[en]);
      }
    }
  }
  
  cout << dp[1][n] << endl;
 }

배운점

• Top-down 방식 DP를 배우고 익힐 수 있었습니다.
• 아직 DP는 갈길이 멀다고 생각했습니다. (흑흑)

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!