[BOJ]10775번: 공항

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

---

Union-find를 사용한 그리디 알고리즘을 통해 해결할 수 있습니다.

 

어떤 비행기가 1~k번째 게이트에 도킹을 시도할 때 k번째 게이트에 도킹을 시도하는 것이 최적해입니다.

 

다만 k번째 게이트에 도킹을 시도할 때 이미 도킹이 되어있는 경우, 다음 게이트를 찾는 과정을 O(G)에서 시간복잡도를 줄이기 위해 Union-find를 사용합니다. 

그러면 해당 해를 O(P*log(G))에 해결할 수 있습니다.

---

코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ10775.java