[Programmers] 입국심사

문제 : https://programmers.co.kr/learn/courses/30/lessons/43238

---

문제 풀기전에 문제 분류를 봐버렸다..

이분탐색 문제를 풀고싶었다기 보다는 레벨3 문제를 풀고싶었던건데 문제분류가 너무 잘보여버림.

 

이분탐색이란걸 알았으니 어떻게 이분탐색으로 해야하는지 분석해보자.

입국심사를 기다리는 사람은 최대 10억명. 한 명의 심사관이 걸리는 시간은 최대 10억분. 심사관의 수는 최대 10만.

이분탐색은 내부 조건이 정답이 가능한지 안한지를 판단할 수 있어야한다.

그럼 주어진 조건을 어떻게 정답이 되는지 안되는지 알 수 있을까.

m분안에 모든 심사원이 최소 n명을 처리할 수 있다면 m분이 정답이 될 수 있다.

모든 심사원이 처리할 수 있는 시간 = 각 심사원들이 m분안에 처리할 수 있는 사람들의 수 = SUM(m / times[i]) 

만일 이 시간이 n 보다 같거나 크다면 n명을 m분안에 처리가능하다.

 

즉, 정답이 가능한 분의 최소를 left, 최대를 right로 만들어서 m = (left + right) / 2. 인 m분안에 모든 심사원이 처리할 수 있는 시간이 n보다 크거나 작다면 정답을 m으로 갱신. 범위를 줄여서 다시 탐색하기 위해 right = m-1 로 갱신. n보다 작다면 불가능한 경우이므로 left = m + 1로 갱신.

위 과정을 left <= right 동안 반복한다.

 

정답가능한 분의 최소는 0분이라 하면, 최대는 얼마일까.

최악의 경우는 times 값을 참고해도 되지만 그냥 폭 넓게 모든 사람을 심사하는데 10억분이 투자되는 경우(10억 * n)를 최대값으로 잡아서 풀었다.

 

시간복잡도는 left, right를 바꿔가면서 반복하는 횟수 O(log2 (10억 * n)) x 모든 심사원이 처리할 수 있는 시간을 구하는데 드는 시간인 O(|times|).

상수는 생략이 가능하므로 O(log(n) * |times|).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/Binary-search/%EC%9E%85%EA%B5%AD%EC%8B%AC%EC%82%AC.cpp