이분탐색. [1253]

[1. 문제 설명]

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

---

[2. 풀이 접근]

풀이 시 주의 할점

• std::lower_bound  에 대응되는 sort.Search() 는 하한 값 중 가장 먼저 오는 index 를 반환한다.
• 중복된 값에 대해서도 확인이 필요한 경우, upper_bound 에 해당하는 index 까지 구할 필요가 있다.
• 즉, [lo, hi) 까지 순차적으로 확인 해 볼 필요가 있다.

시간 복잡도는 O(N^2 logN) 인데,

N 의 최대가 2,000 이므로, 현실적인 시간 내에 해결 가능하다. 

---

[3. 코드]