백준 16225 - 제271회 웰노운컵

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

아이디어

우리는 저 숫자들을 괄호 집합으로 볼 것이다. 그러면 높은 합을 만들어내면서도 올바른 괄호 집합을 유지해야 하는 문제로 바뀐다.

 

문제를 보면 "내가 두 문제를 고르면 Etacoder Plus는 당연히 더 높은 B값을 가지는 문제를 가져갈 것이다."로 인해 B가 가장 높은 값은 Etacoder가 가져가고 B가 제일 낮은 값은 내가 가져감을 이해할 수 있다.

 

잘 이해가 가지 않는다면 곰곰히 생각해보자. 어떻게 해서든 내가 B가 제일 높은 값을 가져갈 수 없다는 사실을 깨우치면 이해할 수 있다.

 

그러면 주어진 pair 수열을 B의 오름차순으로 정렬하고 내가 가져가는 문제를 여는 괄호라 하고 상대가 가져가는 문제를 닫는 괄호라고 할 때 B의 최소와 B의 최대에 괄호를 그려보자.

 

 

그럼 위와 같이 일단 괄호로 감싸진 모양이 등장한다. 그러면 우리는 나머지 N - 2개의 수들에 대해 올바른 괄호 집합을 만들면서 우리에게 이득인 문제를 가져가도록 하면 되는 것이다.

근데 왜 괄호죠?

사실 이렇게 크면서도 올바른 괄호 집합을 만드는 문제는 $O(N^{2})$ DP로 풀 수 있는 문제로 알려져있다고 한다. 그런데 수가 매우 크므로 그것보다 작은 시간 복잡도로 문제를 풀어야 하는 것이다.

괄호 집합을 만들지 않는다고 했을 때...

괄호 집합을 신경쓰지 않고 그냥 N - 2개 중 A가 큰 $\frac{N - 2}{2}$개를 가져가면 어떤 일이 일어날까?

 

이를 살펴보기 위해 이 포스트에서는 2개의 테스트 케이스를 제공하고 어떻게 되는지 괄호를 그려볼 것이다.

 

10
6 13 8 10 13 2 8 11 13 11
3 5 6 8 8 11 12 14 14 15

15
9 13 9 24 11 26 22 27 2 22 28 30 2 7 3
8 24 26 13 5 22 16 23 4 5 22 3 17 5 30

 

이 중에서 위에껄 보자. 단순하게 A가 큰 $\frac{N - 2}{2}$개를 가져가면 다음과 같은 일이 생겨난다.

 

 

이처럼 올바른 괄호 집합이 만들어지지 않고 따라서 해당 방법은 모순이 발생함을 알 수 있다. 그러면 어떻게 해야 할까?

괄호 집합을 충족하는 최적해

괄호 집합이 올바르기 위한 조건 하나를 더 만들어낼 수 있다.

 

모든 홀수 길이 접두사에 대해 여는 괄호의 갯수는 닫는 괄호의 갯수보다 많다.

 

이를 이용해서 다음과 같은 전략으로 올바른 괄호 집합을 유지하면서 큰 값을 만들 수 있다.

 

1. 인덱스 2부터 시작한다.(인덱스 0은 여는 괄호이다.)

 

2. 인덱스 i와 인덱스 i - 1의 A값을 max heap에 넣고 큰 값을 하나 가져간다. 그러면 값을 취한 인덱스는 여는 괄호가 된다. 그러면 위 조건에 의해 올바른 괄호 집합이 유지됨을 확인할 수 있다.

 

3. 인덱스 N - 1까지 인덱스를 2씩 증가하면서 2를 시행한다.

 

4. 이렇게 해서 취하지 않은 인덱스를 닫는 괄호로 두면 올바른 괄호 집합이 된다.

 

위 과정을 잘 구현하면 정답을 받을 수 있다.

 

전체 코드

#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>;
 
pii ar[200000];
int n;
 
void solve()
{
  cin >> n;
  for (int i = 0; i < n; i++) cin >> ar[i].first;
  for (int i = 0; i < n; i++) cin >> ar[i].second;
  sort(ar, ar + n, [](pii &l, pii &r) {
    return l.second < r.second;
  });
  ll ans = ar[0].first;
  priority_queue<int> pq;
  for (int i = 2; i < n - 1; i += 2)
  {
    pq.push(ar[i].first);
    pq.push(ar[i - 1].first);
    ans += pq.top();
    pq.pop();
  }
  cout << ans;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록