[C++] 16566번: 카드 게임

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

16566번: 카드 게임

 

 

 - 관찰

예제 입력 1의 카드들을 정렬해보면 다음과 같다.

2 3 4 5 7 8 9

이제 K번 주어지는 철수가 내는 카드들을 살펴보자.

4를 내면 5가 나와야하고, 1을 내면 2가 나와야한다. -> 이진탐색 lower_bound를 입력값 + 1에 대해 해준다.(4를 냈다면 5를 찾는 탐색을 진행)

 

다음으로 카드가 1 2 3 4가 있는데, 0을 4번 내는 경우를 가정해보자. 이것의 출력은 1 2 3 4가 될 것이다.

1 2 3 4에서 1을 내게 되면 1에 '어떤 처리'를 해주어야할 것이다. 그 다음에 두번째로 0을 이진탐색했을 때 방금 냈던 1을 반환하게 될 텐데, 이것은 결국 2로 연결지어야한다. 세번째로 0을 내면 1이 반환되고 3을 내고, 네번째로 0을 내면 똑같이 1이 반환되고 4를 내게 된다.

이걸로 다음과 같은 그림을 상상해볼 수 있다.

빨간색은 이진탐색으로 반환된 원소이며, 파란색은 '집합'을 말한다.

즉, 처음 이진탐색으로 1이 반환되면 그것을 출력한 뒤, 1의 바로 다음 원소인 2와 묶는 식이다. 즉, 유니온 파인드를 사용하게 된다.

단, 조금 다른 점은 find 함수를 쓰면 집합에서 가장 큰 수를 반환한다는 점이다.

 

이것을 일반화하여, 한 카드에 대한 카드를 낼 때 어떻게 코드를 짜야할지 설명하겠다.

0. 유니온파인드의 parents 함수는 인덱스 기준으로 초기화한다. parents[0] = 2라면, 0번째 원소가 2번째 원소로 묶여있다는 것이다.

1. 우선, 이진탐색(lower_bound)로 상대가 낸 카드를 검색하여 인덱스를 가져온다.

2. 위의 인덱스에 대해 find 함수를 사용한다. 검색된 카드가 어떤 카드와 묶여있는지를 알아보는 것이다. 이후 함수의 결과인 인덱스를 참조하여 출력해준다.(nums[findParent(index)])

3. 카드를 사용하였으므로 다음 카드와 union해준다. findParent로 접근해주어야 한다는 점과, index의 범위가 끝일 경우에는 이 작업을 하면 안 된다는 점에 유의하자.

 

 - 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int parents[4000001];

int findParent(int x) {
	if (parents[x] == x) return parents[x];

	return findParent(parents[x]);
}

void unionParents(int x, int y) {
	int xParent = findParent(x);
	int yParent = findParent(y);

	if (xParent < yParent) parents[xParent] = yParent;
	else parents[yParent] = xParent;
}

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

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

	// Set nums
	vector<int> nums;
	for (i = 0; i < M; i++) {
		int tmp;
		cin >> tmp;
		nums.push_back(tmp);
	}
	sort(nums.begin(), nums.end());

	// Init parents
	for (i = 0; i < M; i++) parents[i] = i;

	// Solution
	for (i = 0; i < K; i++) {
		int tmp;
		cin >> tmp;
										 
		int index = lower_bound(nums.begin(), nums.end(), tmp+1) - nums.begin();
		cout << nums[findParent(index)] << "\n";

		if (index <= M-1) unionParents(findParent(index), findParent(index) + 1);
	}
}