1. 문제
https://www.acmicpc.net/problem/10775
10775번: 공항
문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다. 이렇게 공항을 운영할 경우 간혹 비행기가 어떤 곳에도 도킹하지 못하는
www.acmicpc.net
2. Note
gi가 주어졌을 때 가능한 gi에 가깝도록 게이트를 배정해야하고, 이를 위해 가까운 게이트를 탐색해야 한다는 것은 파악하였다.
그러나 효율적으로 탐색하는 방법을 떠올리지 못했다.
최적화된 Disjoint Set을 사용하면 된다고 한다.
3. Reference
https://www.geeksforgeeks.org/union-find/
Disjoint Set (Or Union-Find) | Set 1 (Detect Cycle in an Undirected Graph) - GeeksforGeeks
A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. A… Read More »
www.geeksforgeeks.org
https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Time_complexity
Disjoint-set data structure - Wikipedia
MakeSet creates 8 singletons. After some operations of Union, some sets are grouped together. In computer science, a disjoint-set data structure (also called a union–find data structure or merge–find set) is a data structure that tracks a set of elements p
en.wikipedia.org
'Problem Solving' 카테고리의 다른 글
| [BOJ11004] K번째 수 (K-th smallest) (0) | 2020.03.19 |
|---|---|
| [BOJ2749] 피보나치 수 3 (0) | 2020.03.16 |
| [BOJ9663] N-Queen (0) | 2020.03.02 |
| [BOJ10814] 나이순 정렬 (0) | 2020.03.01 |
| [BOJ2014] 소수의 곱 (0) | 2020.01.24 |