[백준] 공항 (10775번)

문제

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

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

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

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

이렇게 공항을 운영할 경우 간혹 비행기가 어떤 곳에도 도킹하지 못하는 사고가 발생한다. 이러한 사고가 일어나면 공항의 평판이 급속히 나빠져, 이후 어떤 비행기도 도착하지 않으려 할 것이다.

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

입력

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

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

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

출력

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

---

처음엔 문제도 이해가 안 가서 뭔 문젠가 한참 읽어봤다.

순서대로 들어오는 비행기가 1~g 까지의 게이트 중 하나에 도킹할 수 있고,

1~g까지 모든 게이트가 꽉차면 그 순간 더이상 도킹이 불가능하다는 뜻이었다. 

 

해결 방법은 g번 게이트부터 차례대로 도킹시키는 것이다. g번이 차있으면 g-1, g-2, ... ,1번까지 도킹한 후 1번도 차있으면 종료한다.

이걸 구현하는 방법은 도킹시킬 때 g번의 루트와 g-1번의 루트를 합치는 것이다. g번의 루트가 0이 아니라면 도킹할 수 있는 게이트가 적어도 한 개는 남았다는 뜻이므로 도킹시키고, 0이라면 즉시 종료한다.

 

union - find 함수 자체는 간단하기 그지없지만 생각할 여부가 있는 문제였다.

 

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EA%B3%B5%ED%95%AD%20(10775).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int G, P;
int parent[100001];

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

void Union(int u, int v) {
	u = find(u);
	v = find(v);
	parent[u] = v;
}

int main()
{
	cin >> G >> P;
	for (int i = 1; i <= G; i++) parent[i] = i;

	int g;
	int res = 0; 

	while (P--) {
		cin >> g;
		if (find(g) == 0) break;
		else {
			res++;
			Union(find(g), find(g) - 1);
		}
	}
	cout << res;
}