✓

태그:

CLASS 5

비행기가 한 대씩 순차적으로 공항의 게이트에 도킹하는 상황에서 각 비행기마다 도킹할 수 있는 최대 게이트가 주어졌을 때, 최대로 도킹할 수 있는 비행기의 대수를 구하는 문제입니다. 문제의 조건을 다시 생각해보면, 비행기가 순서대로 들어오면서 도킹할 수 있는 최대 게이트 번호가 주어집니다. 즉, 비행기가 도킹하는 적당한 규칙을 설정하면 뒤에 들어오는 비행기의 번호에 상관없이 앞에 들어오는 비행기의 번호에 따라 도킹할 게이트를 정할 수 있겠습니다.

먼저 작은 번호의 비행기가 도킹한 후 큰 번호의 비행기가 들어오는 경우 어차피 뒤 비행기가 도킹할 수 있는 게이트가 하나 줄어드므로 신경을 쓸 필요가 없겠습니다. 반대로 큰 번호의 비행기가 도킹한 후 작은 번호의 비행기가 도킹하는 경우, 앞 비행기가 뒤 비행기의 번호보다 큰 값의 게이트에 도킹하면 작은 번호의 비행기가 도킹할 수 있는 경우의 수가 늘어나므로 이왕이면 큰 번호의 게이트에 도킹하는 것이 좋을 것 같습니다. 결론은 도킹 가능한 게이트 중 가장 큰 번호의 게이트에 도킹하는 것이 좋을 것 같습니다.갑자기?? 이제 이 규칙에 따라 비행기를 도킹시키되 더 이상 비행기를 도킹하지 못할 때까지 도킹한 비행기의 수를 출력하면 됩니다.

도킹할 게이트를 지정하는 방법은 분리 집합을 사용할 수 있겠습니다. 집합의 루트는 항상 가장 작은 번호의 게이트로 설정하면 최대 게이트로 지정된 번호보다 작거나 같은 수 중 도킹할 수 있는 가장 큰 게이트 번호를 빠르게 구할 수 있습니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-03-10 23:17:20

---