[BOJ] 10775

less than 1 minute read

공항

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

gi이하의 게이트에만 도킹할 수 있으므로
도킹 할 수 있는 게이트들 중 번호가 가장 큰 게이트에 도킹해야 함을 알 수 있습니다.

STL을 이용해 최적의 게이트를 제거해가는 방식으로 해결이 가능합니다.
또한, 경로 압축을 위한 union find를 이용한 방식으로도 해결이 가능합니다.
(하나하나 번호가 큰 게이트부터 확인해가면 O(N2)으로 시간초과가 날 수 있습니다.)

정답 코드
STL을 이용한 방식 https://github.com/Geniemo/BOJ/blob/master/10775_1.cpp
union find를 이용한 방식https://github.com/Geniemo/BOJ/blob/master/10775_2.cpp

Categories:

Updated:

Leave a comment