[BOJ] 10775번: Gates

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

조금만 관찰을 해보면 비행기를 가능한 뒤에 배치하는 것이 무조건 이득임을 알 수 있습니다. 그러면 비행기가 담겨있는지를 가지고 있는 arr라는 배열을 생각했을 때, 입력받은 g_i에 대해 arr[g_i]가 false인지, arr[g_i-1]이 false인지 ,... 이렇게 따져서 false인 것을 찾아 비행기를 배치하면 됩니다. 그런데 이 때 정직하게 매번 1씩 줄여가며 탐색을 하면 O(N^2)이 될 수 있습니다. 그렇기에 union find로 경로 압축을 해주어야 합니다.

https://github.com/blisstoner/BOJ/blob/master/10775.cpp