백준 16566번 카드 게임[C++]

1. 문제 풀이

 안녕하세요? 이번 문제의 유형은 서로소 집합(disjoint-set)입니다. 백준에서는 분리 집합으로 분류되고 유니온-파인드라고도 합니다. 민수는 철수가 낼 카드보다 큰 카드가 있다면 그 카드들 중 가장 작은 카드를 항상 내야합니다. 이는 이분 탐색의 upper_bound를 설명하고 있습니다. 따라서 관련 접근법을 생각하던 도중, 이미 냈던 카드는 다시 사용할 수 없다는 조건이 있어 upper_bound를 그대로 사용하기엔 적절하지 않음을 파악했습니다.

 이를 해결하기 위해 서로소 집합을 사용하면됩니다. 서로소 집합에서 사용하는 부모 배열 p를 iota로 값을 할당하는데 각 vertex에 대해서 다음 카드를 가리키게 구현했습니다.

vector<int> card(4'000'001);
...
iota(card.begin(), card.end(), 1) // card[x] = x + 1 값을 가지게 됨.

그 다음 M개의 카드의 각 번호 xi에 대해서 card[xi] = xi 값으로 다시 갱신해주고 경로 압축을 구현하는 find 함수만 있으면 이 문제를 해결할 수 있습니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

vi card(4'000'001);
int n, m, k;

int find(int x) {
    return (card[x] == x ? card[x]++ : card[x] = find(card[x]));
}

int main() {
    fastio(nullptr, false);

    cin >> n >> m >> k;

    iota(all(card), 1);
    
    for(int i = 0; i < m; i++) {
        int x; cin >> x;
        card[x] = x;
    }

    for(int i = 0; i < k; i++) {
        int x; cin >> x;
        cout << find(x+1) << nl;
    }
}

 

3. 제출 결과