[백준] 10775번: 공항

📌 문제

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

📌 설명

각 비행기에 대하여 가능한 게이트를 확인하는 방법(O(GP))은 시간 초과가 발생한다. 분리 집합을 통해 비행기가 들어갈 수 있는 게이트를 계속 초기화를 해야 한다. 구체적인 방법은 다음과 같다.

1. 각 게이트의 부모를 자신의 번호로 설정한다.

2. 비행기가 들어갈 수 있는 게이트의 최대 번호 x를 입력받고, 실제로 들어갈 수 있는 게이트의 최대 번호 px를 구한다(Union-Find의 Find).

3. 만약 0이라면 중단, 그렇지 않다면 Union(px, px - 1)을 통해 비행기가 들어갈 수 있는 게이트의 번호를 초기화한다.

x = 5, parents[x] = 3이라고 하면, 이 비행기는 1번부터 5번 게이트에 들어갈 수 있으나 다른 비행기가 있기 때문에 1번부터 3번 게이트에 들어갈 수 있는 상황이다. 이 비행기는 3번 게이트에 들어가는 것이 유리하다. 그렇다면 다음 비행기 중 3번 이상의 게이트에 들어가는 비행기가 들어갈 수 있는 게이트를 2번 게이트까지로 제한해야 한다. 이 기능을 Union(px, px - 1)이 수행한다.

📌 코드

#include <iostream>

using namespace std;

int parents[100001];

int Find(int x) {
	if (parents[x] == x)
		return x;
	else
		return parents[x] = Find(parents[x]);
}

void Union(int x, int y) {
	int px = Find(x);
	int py = Find(y);

	if (px < py)
		parents[py] = px;
	else
		parents[px] = py;

}

int main() {
	int g, p;
	cin >> g >> p;

	for (int i = 0; i <= g; i++) {
		parents[i] = i;
	}

	for (int i = 0; i < p; i++) {
		int x;
		cin >> x;

		int px = Find(x);

		if (px == 0) {
			cout << i;
			return 0;
		}
		else {
			Union(px, px - 1);
		}
	}
	cout << g;
}