[백준] 11066번: 파일 합치기 (C++)

문제 링크

11066번: 파일 합치기

---

어제 쓴 포스팅(행렬 곱셈 순서)에 이어서, 비슷한 유형의 문제가 있기에 풀어봤습니다.

유형은 똑같은데 다른 점이 딱 하나 있었습니다. 저는 그 다른 점을 찾지 못해서 결국 구글링을 통해 알아냈습니다.....

자세한 설명을 해주신 블로그 글의 주인분께 감사의 인사를 드립니다.

풀이

트리형태 DP + 누적합 DP를 사용하여 풀이하면 됩니다.

트리형태 DP라는 의미는 어제 쓴 포스팅(행렬 곱셈 순서)를 참고해 주시면 될 듯합니다.

전에 푼 문제와 같이 `left`, `root`, `right` 를 통해 문제 풀이를 해결해야 했는데,

저는 처음에 단순히 `root` 를 `files[mid] + files[mid+1]`으로 놓고 풀이를 했었습니다.

하지만 위 방식은 단순히 mid에 있는 값만을 참조해서 더하는 것이기 때문에, 정확한 값을 내보내기엔 어려움이 있습니다.

(중복된 값이 더해질 수도 있고, 누적합이 아니기 때문에 더 작은 값으로 결과가 나올 수도 있습니다.)

이를 해결하기 위해서는 누적합(`sum`)의 개념을 사용해서 문제를 풀이해야 합니다.

\[ sum[i] = sum[i - 1] + files[i] \]

이 누적합을 통해 임시파일의 모든 값을 더해서 나온 DP식을 만들면 됩니다. 최종 DP 식은 다음과 같습니다.

\[ dp[st][en] = dp[st][mid] + dp[mid + 1][en] + (sum[en] - sum[st - 1]) \]

풀이코드

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

#define endl "\n"

int n;
int files[501];
int dp[501][501];
int sum[501];

int go(int st, int en) {
  if (st >= en) return dp[st][en] = 0;
  if (dp[st][en] != 1e9) return dp[st][en];

  for (int mid = st; mid < en; mid++) {
    int left = go(st, mid);
    int root = sum[en] - sum[st - 1];
    int right = go(mid + 1, en);
    dp[st][en] = min(dp[st][en], left + root + right);
  }

  return dp[st][en];
}

void solve() {
  int t;
  cin >> t;
  while (t--) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> files[i];
      fill(dp[i], dp[i] + n + 1, 1e9);
      sum[i] = sum[i - 1] + files[i];
    }

    cout << go(1, n) << endl;
  }
}

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;
}

사실 저도 누적합을 왜 사용하는지 완벽히 이해가 가진 않았습니다만, 직접 그림을 그려보며 생각해보니 어느정도 이해는 됐습니다.

무작정 모든 값을 더해서 최종 값을 구하는 것이 아니라, 만들어진 트리 DP에 있는 모든 값을 더해야 되기 때문에 누적합을 했어야 했던 것입니다.

배운점

• 누적합을 복습할 수 있었습니다.
• 해당 문제 형태의 DP를 복습할 수 있었습니다.

 

---

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

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