백준 10775

_Bibidi 2021. 1. 21. 00:10

10775번: 공항

예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불

www.acmicpc.net

빈 방에 비행기를 채워 넣는 문제입니다. 숫자가 작은 방일수록 더 많은 종류의 비행기를 넣을 수 있으므로 g_i보다 같거나 작은 빈 방 중 가장 큰 빈 방부터 써야 합니다. 이걸 어떻게 구현할 수 있을까요 ?

처음 set에 빈 방을 모두 넣어줍니다. 이때 set이 내림차순이 되도록 설정하면 set.lower_bound(t)를 이용하여 t와 같거나 작은 방을 logN에 찾을 수 있습니다. g_i보다 같거나 작은 방 중 가장 큰 방을 찾으면 그 방을 빼버리고, 남아있는 방을 찾을 수 없다면 종료하고 답을 출력하면 됩니다.

- Source code link

github.com/Bibidi/Algorithms/blob/master/boj/boj%2010775.cpp