백준 16566 카드 게임 (c++) : 피너클

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

16566번: 카드 게임

이진탐색과 유니온 파인드를 이용한 문제다.

내가 낼 수 있는 카드중에서 민수를 이길수있는 가장 작은 카드를 내면 된다.

int n, m, k;
int parent[4000001];
vector<int> v;
vector<int> ::iterator it;

사용할 변수다.

parent는 조상을 담을것이고 it은 이진탐색에 사용할것이다.

int find(int num) {
	if (parent[num] == num) return num;
	else return parent[num] = find(parent[num]);
}

find함수다. num의 조상을 반환한다.

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

merge함수다. 두 정수를 합친다.

cin >> n >> m >> k;
for (int i = 0; i < m; i++) {
	int a;
	cin >> a;
	v.push_back(a);
	parent[i] = i;
}
sort(v.begin(), v.end());

이제 main함수에서 숫자를 입력받으며 parent를 초기화하고 v를 정렬한다.

for (int i = 0; i < k; i++) {
	int a;
	cin >> a;
	int idx = find(upper_bound(v.begin(), v.end(), a) - v.begin());
	cout << v[idx] << '\n';
	merge(idx, idx + 1);
}

그후 민수가 내는 카드들을 입력받으며 v에서 민수보다 큰 카드중 가장 작은 카드의 위치를 idx에 담는다.

idx에 저장할때 find함수를 써서 담는걸 알수있다.

lower_bound가 아닌 upper_bound로 하는 이유는 들어온 카드를 초과하는 숫자를 내야하기 때문이다.

그후 v[idx]를 출력한뒤 idx와 idx+1을 합친다.

현재 예제에 나와있는 상태다. 검은색은 카드의 숫자, 빨간색은 카드의 조상을 의미한다.

처음에 민수가 4를 냈으니 우리는 카드 5를 낼것이다. 그후 우리는 5와 7을 합친다.

이제 5카드를 쓸수 없는데 또다시 숫자 4가 들어온다면 우리는 어떻게 해야할까? 

5의 조상을 찾아가면 된다. 위를 보면 5의 조상은 7로 되어있다. merge(idx, idx + 1)을 했기 때문이다.

그럼 또다시 4가 들어온다면?

이번에는 8이 출력될것이다. 이를 반복하면 된다.

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

using namespace std;

int n, m, k;
int parent[4000001];
vector<int> v;
vector<int> ::iterator it;

int find(int num) {
	if (parent[num] == num) return num;
	else return parent[num] = find(parent[num]);
}

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

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

	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		int a;
		cin >> a;
		v.push_back(a);
		parent[i] = i;
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < k; i++) {
		int a;
		cin >> a;
		int idx = find(upper_bound(v.begin(), v.end(), a) - v.begin());
		cout << v[idx] << '\n';
		merge(idx, idx + 1);
	}
}

전체코드다.