플래5 - 백준 16566 카드 게임

백준 16566 카드 게임

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

접근방법

이 문제는 주어진 수들 중에서 입력된 수보다 큰 수를 출력하는 문제로 분리집합을 이용하여 간단하게 해결하였다.

풀이

현재 가지고 있는 카드는 usable배열에 true, false로 사용 가능 여부를 나타내주었고, 범위인 4백만개 만큼 cards배열을 만들고 값을 현재 갖고 있는 카드들 중 인덱스값보다 큰 수를 가리키게끔 초기화 하였다. 그리고 수를 입력받으면서 merge 재귀함수로 usable배열을 체크하면서 민수가 낼 수 있는 카드를 구해주고 cards 배열의 가리키는 값들을 갱신해준다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int cards[4000001];
bool usable[4000001];
vector<int> select_cards;

int merge(int node)
{
	if (usable[cards[node]])
	{
		usable[cards[node]] = false;
		return cards[node];
	}

	return cards[node] = merge(cards[node]);
}

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

	int N, M, K;
	cin >> N >> M >> K;

	for (int i = 0; i < M; i++)
	{
		int temp;
		cin >> temp;
		select_cards.push_back(temp);
	}

	sort(select_cards.begin(), select_cards.end());

	int index = 1;
	for (int i = 0; i < select_cards.size(); i++)
	{
		int cur = select_cards[i];
		usable[cur] = true;

		while (index <= N) {

			if (index >= cur)
				break;
			cards[index] = cur;
			index++;
		}
	}

	while (K--)
	{
		int card_num;
		cin >> card_num;
		cout << merge(card_num) << '\n';
	}

	return 0;
}