백준 4160 - 이혼

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

힌트

브루트 포스를 시행하면 $3^{24}$만큼 경우의 수가 있다.

 

밋 인 더 미들을 통해 $O(3^{12})$로 풀 수 있다.

풀이

다음 3가지를 한 번에 고려해보자.

 

잭이 가지는 집의 가치

질이 가지는 집의 가치

판매하는 집의 가치

 

3가지를 각각 따져서 브루트 포스로 잭의 집 가치와 질의 집 가치가 같은 경우를 찾으면 $3^{24}$만큼 경우의 수가 나오고 이는 매우 커서 30초라는 제한 시간 안에 어림도 없음을 알 수 있다.

 

밋 인 더 미들을 기법을 사용해 주어진 집을 2개의 부분 집합으로 쪼개자. 그러면 각 집합의 크기는 최대 12가 된다. 이때 우리는 다음을 구할 것이다.

 

분할된 집합을 각각 $s_{1}$, $s_{2}$라고 하자. $s_{x}$에서 집을 배분하는 i번째 조합 $s_{x, i}$에 대해 잭의 집 가치와 질의 집 가치의 차이를 $s_{x, i}(|value|)$라고 하고 판매하는 집의 가치를 $s_{x, i}(cost)$라고 하면 $s_{1, i}(|value|) = s_{2, j}(|value|)$ 일 때 $min(s_{1, i}(cost) + s_{2, j}(cost)) (i, j \leq 3^{12})$를 구하는 문제로 바뀐다.

 

각 조합마다 판매하는 집의 가치의 최솟값을 찾으면 제한 시간 안에 여유롭게 정답을 받을 수 있다. 자세한 구현은 밑을 참고한다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/rope>

using namespace std;
using namespace __gnu_cxx;
using ll = long long;
using pii = pair<int, int>;

int n;
int tb;
int sum;
int ar[24];
int ss1[12];
int ss2[12];
int ternary[24];
vector<pii> v1, v2;
int l, r;

void backtrack(int idx, int limit, int type)
{
  if (idx == limit)
  {
    int jack = 0, jill = 0;
    int sell = 0;
    for (int i = 0; i < limit; i++)
    {
      if (ternary[i] == 1)
      {
        if (type == 1) jack += ss1[i];
        else jack += ss2[i];
      }
      else if (ternary[i] == 2)
      {
        if (type == 1) jill += ss1[i];
        else jill += ss2[i];
      }
      else
      {
        if (type == 1) sell += ss1[i];
        else sell += ss2[i];
      }
    }

    if (type == 1)
    {
      v1.push_back({abs(jack - jill), sell});
    }
    else
    {
      v2.push_back({abs(jack - jill), sell});
    }
  }
  else
  {
    for (int i = 1; i <= 3; i++)
    {
      ternary[idx] = i;
      backtrack(idx + 1, limit, type);
    }
    ternary[idx] = 0;
  }
}

void solve()
{
  v1.clear();
  v2.clear();
  l = r = 0;
  tb = (1 << n) - 1;
  int bc = __builtin_popcount(tb) / 2;
  int ans = 1e9;

  for (int i = 0; i < n; i++)
  {
    if (l < bc)
    {
      cin >> ss1[l++];
    }
    else
    {
      cin >> ss2[r++];
    }
  }

  backtrack(0, l, 1);
  backtrack(0, r, 2);
  sort(v1.begin(), v1.end());
  sort(v2.begin(), v2.end());

  for (int i = 0; i < v1.size(); i++)
  {
    auto cur = v1[i];
    int idxl = lower_bound(v2.begin(), v2.end(), cur, [](const pii &l, const pii &r) {
      return l.first < r.first;
    }) - v2.begin();
    int idxr = upper_bound(v2.begin(), v2.end(), cur, [](const pii &l, const pii &r) {
      return l.first < r.first;
    }) - v2.begin();

    for (int j = idxl; j < idxr; j++)
    {
      ans = min(ans, cur.second + v2[j].second);
    }
  }

  cout << ans << '\n';
}

int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  cin >> n;

  while (n != 0)
  {
    solve();
    cin >> n;
  }
}

 

제출 기록