[백준 10775] 공항

문제

www.acmicpc.net/problem/10775

10775번: 공항

 

풀이

i번째 비행기가 들어왔을 때 [1, g_i]게이트 중 어디에 도킹시킬지를 정해줘야 하는데 이는 아래와 같은 예를 떠올려보면 어렵지않게 큰 번호의 게이트부터 채워나가야함을 알 수 있습니다.

 

※ [1, 2, 3]의 게이트가 꽉 찼을 때, g = [5, 4]라면 1번째 비행기를 4번게이트에 두면 2번째 비행기가 도킹x, 반대로 5번게이트에 도킹하면 2번째 비행기가 도킹가능

 

이 때 g를 순회하며 g_i~1까지 비어있는 게이트를 찾아 넣어주면 끝이라고 생각할 수 있지만 O(G^2)으로 시간초과가 나게되므로 다른 방법을 찾아봅시다.

---

1. 게이트에 채워지는 순서에 대해서 생각해보면 높은 번호부터 채워나가기에 낮은 번호의 게이트가 높은 번호의 게이트에 속해있다는 느낌을 줍니다. ( g_1 ⊂ ... ⊂g_G )

 

2. 따라서 이는 기존에 사용하던 유니온파인드 집합에서 parent배열의 의미를 "p[i] = [1, i]에서 비어있는 게이트 중 가장 번호가 높은 것"이라고 정의한 후,  초기 상태는 도킹 하기 전 i번째 게이트를 사용할 수 있으므로 p[i] = i로 초기화 해줍니다.

 

3. 이제 g를 순회하며 i번째 비행기를 도킹하는 공간이 p[g_i]이므로 p[g_i]가 0이라면 그 의미대로 도킹할 수 없는 것이고 0이 아니라면 도킹한 후 p[g_i]를 하나 낮은 게이트번호인 p[g_i] - 1로 갱신해줍니다. 

 

4. 유니온 파인드에서 가장 상위부모를 구할 때 경로압축을 사용하지 않으면 결국 다시 O(G^2)이 걸리기에 상위 부모를 구할 때 경로압축을 사용해서 해결할 수 있습니다.

 

코드

#include <bits/stdc++.h>
using namespace std;
 
int G, P, ipt, ans;
vector<int> p;
 
int find(int x) {
	if (p[x] == x) return x;
	return p[x] = find(p[x]);
}
 
int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);
 
	cin >> G >> P;
	p.resize(G + 1);
	for (int i = 1; i <= G; i++) p[i] = i;
	for (int i = 0; i < P; i++) {
		cin >> ipt;
		int k = find(ipt);
		if (!k) break;
		p[k] = k - 1;
		ans++;
	}
	cout << ans;
}