BOJ 16566 : 카드 게임

• 문제 링크 : boj.kr/16566
• 난이도 : P5
• 태그 : 이분탐색, 유니온파인드

16566번: 카드 게임

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int p[4000001];

int find(int u){
    if(u == p[u]) return u;
    return p[u] = find(p[u]);
}

void merge(int u){
    int v = u + 1;
    u = find(u), v = find(v);
    if(u == v) return;
    p[u] = v;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m, k;
    cin >> n >> m >> k;
    vector<int> arr(m);
    for(auto &u : arr) cin >> u;
    for(int i = 0; i < m; i++) {
        p[i] = i;
    }
    sort(all(arr));
    for(int i = 0; i < k; i++) {
        int input;
        cin >> input;
        auto iter = upper_bound(all(arr), input);
        int index = find(iter - arr.begin());
        cout << arr[index] << "\n";
        merge(index);
    }

    return 0;
}

---

풀이

내야 할 카드를 이분탐색으로 찾는다는 것은 쉽게 생각할 수 있을 것이다.

이미 낸 카드를 어떻게 처리할 것인지가 문제이다.

유니온 파인드를 응용해서 해결할 수 있다.

연속된 이미 낸 카드를 하나의 집합으로 보고, 그 다음의 내지 않은 카드를 루트로 보아 유니온 파인드를 시행하면 된다.