BOJ 16225 제271회 웰노운컵

📝 문제 정보

#

• 링크: https://www.acmicpc.net/problem/16225

🧐 관찰 및 접근

#

• 약간 게임이론적이네.
  • $(A_i, B_i), (A_j, B_j)$ 두가지를 고른다.
  • 이때, $B_i > B_j$라면 $A_j$, $B_i < B_j$라면 $A_i$를 얻게된다.
• 직관적인것들을 생각해보자.
  • $A_i$가 크고, $B_i$가 작은것들이 있으면 좋겠다.
    • 위 친구들을 $A_i$가 작거, $B_i$가 큰 친구들이랑 매칭시켜서 없애버리면 좋다.
  • $B$가 가장 작은 문제는 언제나 내가 풀게 된다.
    • $B$가 가장 큰 문제는 언제나 상대가 풀게 된다.
    • 이쪽에서 출발해볼까?
  • $B$에 대한 오름차순으로 정렬해보자. 그러면 버릴 문제를 하나 고를 수 있다.
  • 일단 예제를 $B$에 대한 오름차순으로 정렬한 후, $A$만 남기면
    • $(2, 4, 8, 6)$ 이 된다.
      • 이때 2를 택하고 4를 버려고, 8을 택하고 6을 버리면 10이 된다.
    • 여러개로 생각해보니, 약간 올바른 괄호 문자열 맛으로 되는데…
      • 20만 $O(N^3)$ DP는 안된다이
      • $\text{DP}[i][j]$: $i$번째까지 봤을때, 여는괄호가 $j$개일때 최댓값 이라고 하면 $O(N^2)$도 된다만…
    • 근데 열리는 괄호는, 생각보다 빠르게 열어줘야한다.
      • 1번을 먹었으니, $(2, 3)$중에 하나는 무조건 열어야 한다.
        • $2$를 먹었다면, $3, 4, 5$중 하나는 무조건 열어야 한다.
        • $3$을 먹었다면, $2, 4, 5$중 하나는 무조건 먹어야 한다.
      • $k$개 먹었다면, $2 \leq i \leq 2*k + 1$ 범위 내에서 한개를 더 먹어줘야한다.
        • 이때 최댓값을 먹어줘야하고, 점 업데이트가 있으니 세그먼트 트리로 되겠다.
          • 세그워킹 ㄱ.ㄱ

💻 풀이

#

• 코드 (C++):

void solve(){
    int N; cin >> N;
    vector<pii> A(N);
    rep(i, 0, N) cin >> A[i].first;
    rep(i, 0, N) cin >> A[i].second;
    sort(all(A), [](pii a, pii b){
        return a.second < b.second;
    });
    vector<ll> v;
    rep(i, 0, N) v.push_back(A[i].first);

    ST.init(N);
    rep(i, 0, N) ST.set(i, v[i]);
    ST.build();

    ll ans = v[0];
    rep(i, 1, N/2){
        auto [val, idx] = ST.seg_walk(1, i*2);
        ans += val;
        ST.update(idx, 0);
    }
    cout << ans << '\n';
}