16566 카드 게임

Link

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

Detail

결국 입력으로 가진 카드를 받고, 주어지는 Input마다 upper_bound 값을 찾아 반환하면 된다.

Union_Find 방식을 사용해서 Table[i] = i 보다 큰 최소의 카드를 저장하여 해결했다. 카드를 사용했을 경우 Table[card]의 값을 1늘려서 체인을 걸면 해결할 수 있다.

# Code

#include<bits/stdc++.h>
 
#define MAX 4000000
#define FAST_IO ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
 
using namespace std;
 
// Table[i] = 가진 카드 중 i보다 크거나 같은 최소의 카드
vector<int> Table;
int N, M, K;
 
int get_min_big(int number) {
	if(Table[number] == number) {
		return number;
	}
 
	return Table[number] = get_min_big(Table[number]);
}
 
void set_table() {
    vector<int> cards(M);
 
    for(int i = 0; i < M; i++) {
        cin >> cards[i];
    }
 
    sort(cards.begin(), cards.end());
 
    int cur_card = 0;
    for(int i = 1; i <= MAX; i++) {
        if(i > cards[cur_card]) {
            if(cur_card == M - 1) {
                break;
            }
            cur_card++;
        }
 
        Table[i] = cards[cur_card];
    }
}
 
int main() {
    FAST_IO;
 
    cin >> N >> M >> K;
    Table.resize(MAX + 1);
 
    set_table();
 
    int target;
    for(int i = 0; i < K; i++) {
        cin >> target;
 
        if(Table[target] == target) { 
        // 예외 케이스 : Table은 "이상"을 기준으로 하나, 
        // 문제에서는 초과하는 숫자를 가진 값을 정답으로 반환해줘야 함
        // 따라서 이 경우 문제가 되는 target은 1을 추가해서 계산
            target++;
        }
        int card = get_min_big(target);
        Table[card] = get_min_big(card + 1);
 
 
        cout << card << '\n';
    }
 
}