탐욕법. [1946]

[1. 문제 설명]

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

---

[2. 풀이 접근]

서류 순위

D F A C E G B

G C B D F A E

면접 순위

 

D 는 서류 순위가 제일 높으므로, 면접에 관계 없이 뽑을 수 있다.

F 는 D 보다 서류 순위가 낮으므로 면접 순위가 더 높아야 뽑을 수 있지만, 면접 순위도 낮으므로 뽑을 수 없다.

A 도 마찬가지 이유로 뽑을 수 없다.

C 는 D 보다 서류 순위가 낮지만, D 보다 면접 순위는 더 높으므로 뽑을 수 있다.

E 역시 뽑을 수 없다.

G 는 C 보다 면접 순위가 더 높으므로 뽑을 수 있다.

 

한가지 중요한 사실이 있다.

서류 순위 순으로 해당 사람을 뽑을 수 있는지 없는지 결정하는 것은

현재 까지 면접 순위가 어떻게 되느냐 이다.

현재 까지 면접 순위보다 더 높으면, 현재까지 중 가장 안좋아도 뽑을 수 있다는 것이다.

그렇기 때문에, 위 과정을 진행 할 수록, 면접 순위는 점점 좋아질 수 밖에 없다.

 

시간 복잡도 => O(nLogn)

---

[3. 코드]