[C++] 11066 : 파일 합치기

 

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

 

이전 포스트로 "행렬 곱셈 순서"에 대해서 두 가지 방식의 다이나믹 프로그래밍으로 문제를 풀어봤다.

https://gg4ever1724.tistory.com/39

[C++] 11049: 행렬 곱셈 순서

 

이 포스트처럼 이번 파일 합치기 문제도 두 방법으로 풀되, 우선적으로 상향식 방법을 연습하자.

 

알고리즘 분류

• 다이나믹 프로그래밍

 

문제설명

 

문제접근

 어떻게 보면 행렬 곱셈 순서보다는 덜 복잡하다. 예를 들어 다음과 같은 파일이 있다면,

40	30	30	50

 

다음과 같은 방법으로 합쳤을 때 최소이다.

(40 30) , (30 50)

-> 70 80 (합 150)

-> 150 (합 300)

 

우선 딱봐도 완전탐색이 불가능하니 DP로 풀 수 있는지 고려해보자.

 

1. Optimal Substructure가 존재하는가?

 

 v1, v2, v3, v4, v5에 대해 구한다고 가정하고, v1~v3, v4~v5 로 나눈다고 가정하자. 이때 v4~v5에 해당하는 합치기는 유일하게 v4+v5이다. 이를 v22 라고 하자. 한편 v1~v3일 경우 합쳐서 v11이라고 놓으면, v11, v22를 구하는 문제가 되고, 또다시 최적의 조합을 찾으면 되는 구조이므로 최적 부분 구조를 만족한다.

 

2. Overlapping Subproblems가 나타나는가? 

 

 앞서 v1~v3을 구하는 문제를 v11으로 변형했다. 그런데 여기서 구한 값은 v11와 v22을 합치는 데에도 다시 이용된다. 따라서 메모이제이션을 활용할 수 있다.

 

 

그러면 이제 dp의 점화식을 구해 보자. 만약 i에서 j까지의 dp를 구한다고 생각하면, 중간에 mid를 둔 다음에,

i부터 mid까지의 최소 합치기 비용 + mid+1부터 j까지의 합치기 비용 + 덩어리 두 개를 합치는 비용이 든다.

식으로 나타내면 다음과 같다.

 

여기에서 이해를 돕기 위해

왼쪽 최소비용 dp[i][mid] 에  i~mid까지 합

+

오른쪽 최소비용 dp[mid+1][j] 에 mid+1~j까지 합

으로 나타냈다. 여기에서 시그마 두개를 합쳐서 i부터 j까지의 합으로 수정할 수 있다.

 

누적합을 구해야하므로 psum 배열을 이용하면 된다.

 

전체코드

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

int psum[504];
int dp[504][504]; // (i 부터 j 까지 최소 합치는 비용)
int t,k;

int main()
{
  cin >> t;
  while (t--)
  {
    cin >> k;
    memset(psum, 0, sizeof(psum));
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < k; i++)
    {
      int num; 
      cin >> num;
      psum[i+1] = psum[i] + num;
    }

    for (int len = 2; len <= k; len++)
    {
      for (int i = 1; i <= k - len + 1; i++)
      {
        int _end = i + len - 1;
        dp[i][_end] = 1e9;
        for (int mid = i; mid < _end; mid++)
        {
          dp[i][_end] = min(dp[i][_end], dp[i][mid] + dp[mid+1][_end]
                                    + psum[_end] - psum[i-1]);
        }
      }
    }

    cout << dp[1][k] << endl;
  }
}

92ms 안에 정답을 잘 구했다.

 

하향식 방법(Top-Down)

그러면 하향식 방법으로도 풀어보자. 이 부분이 더 직관적일 것이다. 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
void fastIO() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
}

int psum[504];
int dp[504][504]; // (i 부터 j 까지 최소 합치는 비용)
int t,k;

int go(int _left, int _right)
{
  if (_left == _right) return 0;
  
  int& ret = dp[_left][_right];
  if (ret != -1) return ret;

  ret = 1e9;
  for (int i = _left; i < _right; i++)
  {
    ret = min(ret, go(_left, i) + psum[i] - psum[_left - 1]
                  + go(i+1, _right) + psum[_right] - psum[i]);
  }

  return ret;
}

int main()
{
  cin >> t;
  while (t--)
  {
    cin >> k;
    memset(psum, 0, sizeof(psum));
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < k; i++)
    {
      int num; 
      cin >> num;
      psum[i+1] = psum[i] + num;
      dp[i+1][i+1] = 0;
    }

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

 

푼 결과 624ms가 나온다. 아슬아슬하다.

 

되도록이면 어려운 문제일수록 조금씩 합해가면서 답을 구하는, 상향식 방법을 적용할 수 있을지 생각해 보자.