문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43238?language=java

문제 정리

• 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다.
• 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
• 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

문제 해결 방법

문제를 보면 제한 사항이 빡세게 주어져 있다.

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

이런 문제는 0부터 최대 걸릴 수 있는 시간 중에서 조건에 맞는 최소값을 찾아야 하는 문제다.

그냥 for문으로 0부터 찾게 되면 당연히 시간이 어마하게 걸릴 것이다. 최악의 경우 10억까지 찾아야하기 때문이다.

이 때 사용할 수 있는게 이분 탐색이다.

→ 이분탐색

이분탐색을 진행하면서, 해당 시간에 입국심사를 할 수 있는 사람을 계산해서 주어진 n과 비교하면 된다.

처음엔 사람 수를 비교하지 않고 시간을 비교하려고 해서 애를 먹었다.

사람의 제한이 10억이고 심사관의 수 제한이 10만이기 때문에 최소 시간을 계산해서 가능한지 불가능한지 찾는 것은 무리다. 최악의 경우 심사관이 10만명인데 어떻게 10억을 각각 심사관한테 분배해서 최소시간을 구하겠는가...