BOJ 1947 - 신입 사원

문제 링크

---

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

문제 해결

---

1. 지원자들은 서류 점수 등수(A)와 면접 점수 등수(B)를 받는다.

2. 신입 사원이 되기 위해선, 모든 지원자들과 비교했을 때 A와 B가 모두 모자라지 않아야한다. 즉, A와 B와 모두 다른 

   지원자들과 비교했을 때, 같거나 작아야한다. 왜냐하면 A와 B는 점수가 아니라 등수이기 때문이다.

3. 우선 A에 대해서 오름차순 정렬을 한다. 

4. 0번째 지원자는 모든 지원자 중에서 A 등수가 가장 높으므로 1번째 지원자부터 N번째 지원자까지 비교한다.

5. i번째 지원자는 0번째 지원자부터 i-1번째 지원자까지의 B 등수 중 가장 높아야한다. 즉, 0번째 지원자부터 i-1번째 

   지원자까지의 B등수 중 가장 높은 등수(temp)보다 더 높아야한다. 비교 후 temp를 계속 갱신해준다.

 

주의할 점

---

1. N의 최대 값이 100,000이므로 O(NlgN)으로 해결해야한다. 즉, 이중 for loop로 구현하면 시간 초과 발생한다.

※ 정확하고 부드러운 태클은 언제나 환영입니다.