[백준 10775번] 공항

[백준 10775번] 공항

www.acmicpc.net/problem/10775

10775번: 공항

 

 

 문제

 오늘은 신승원의 생일이다.

 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

 신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

 

 입력

 첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

 두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

 이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

 

 출력

 승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

 

 

 풀이

#include <iostream>
using namespace std;

int arr[100001];
int u_find(int a){
	if(arr[a] == a) return a;
	else return arr[a] = u_find(arr[a]);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int G, P; cin >> G >> P;
	for(int i=1;i<=G;i++) arr[i] = i;
	
	int cnt = 0;
	for(int i=0;i<P;i++){
		int a; cin >> a;
		int temp = u_find(a);

		if(a >= temp && temp != 0){
			cnt++;
			arr[temp]--;
		}
		else break;
	}
	cout << cnt;
	return 0;
}

 일단 쉽게 생각해보면 만약 4개의 게이트가 있고, 4개의 비행기가 있다면 비행기를 최대한 뒤에 넣는 것이 현명한 방법일 것이다. 따라서 만약 비행기가 1~i 중 한 게이트에 들어가야 한다면 i 게이트에 넣는 것이 많은 비행기를 도킹시키에 좋다. 이 이론을 바탕으로 arr[i] = i로 설정해 두고, i 게이트로의 도킹을 원한다면 arr[i]의 값을 반환해주면 된다. arr[i] 값은 i 게이트를 원할 때, 도킹할 수 있는 최대의 게이트 번호를 나타낸다. 도킹 이후에는 해당 게이트가 찬 상태이기 때문에 한 게이트 이전으로 설정해두면 된다. 이 게이트가 도킹되어 있는 상태일지라도 u_find 함수를 통해 갱신되며 도킹할 수 있는 최대의 게이트를 가리키게 될 것이다.

 글로 설명하기에 뭔가 어렵지만, 구현하다보면 나름 이해가 되면서 풀렸다. 유니온 파인드에서 보통 작은 수로 합치거나 어떤 조건에 따라 합치게 되는데 이 문제에서는 그냥 바로 이전의 게이트 번호로 합쳐주면 되는 문제이다.