문제

나의 요약

입국심사 기다리는 사람 n명이 있고, 각 심사관이 심사하는데 걸리는 시간 times[]이다. n명이 입국심사를 위해 줄을 서서 기다린다. 한 심사대에서는 동시에 한명만 심사 가능하다. 더 빨리 끝나는 심사대가 있다면 기다렸다가 그곳으로 가서 심사 가능하다.
모든 사람이 심사를 받는데 걸리는 최소 시간을 구하자.

접근방식

더 빨리 끝나는 심사대가 있다면 기다렸다가 그곳으로 가서 심사 가능하다. 라는 부분 때문에, 심사의 선후 관계를 따질 것 없이 단순히 나눗셈으로 몫들만 더해주면 그것이 최대로 심사받는 방식이다. 따라서 심사를 받는 최소 시간을 times의 요소들로 나눈다면, 그 몫들의 합이 n이 나와야 한다.
이제 심사를 받는 최소 시간을 어떻게 고를지 정해야 하는데, 한명을 심사하는데 걸리는 시간이 최대 10^9까지 걸리고, 심사를 받는 사람도 최대 10^9명이니 심사를 받는 최소 시간의 최댓값은 10^9 * 10^9 = 10^18이 된다. 결국 정답은 1~10^18 사이에 있다는 건데... 이렇게 많은 값들 사이에서 찾을 수 있는 방법은 이분탐색 말고는 생각나지 않았다.

풀이

#include <string>
#include <vector>

using namespace std;

long long solution(int n, vector<int> times) {
    long long left = 1, right = 1000000000000000000;
    long long mid;
    while(left <= right)
    {
        mid = (left + right) / 2;
        unsigned long long tmpN = 0;
        for(int i = 0; i < times.size(); i++)
        {
            tmpN += mid / times[i];
            if(tmpN > n) break;
        }
        
        if(tmpN >= n)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    
    return left;
}

1~10^18 사이에서 이분탐색을 진행한다. mid가 심사를 받는 시간이고, tmpN은 mid의 시간동안 심사를 할 수 있는 사람의 수이다. times 배열로 시간을 나누어 각 심사관마다 검사하는 사람을 구하고, 합을 더한다.
이후 tmpN, 즉 심사를 받은 사람이 n보다 같거나 크다면 지금이 최소 시간이 아니라는 뜻이니 이분 탐색의 범위를 아래로 줄인다. 만약 심사를 받은 사람이 n보다 작다면 지금이 최소 시간보다 더 작다는 뜻이니 이분 탐색의 범위를 위로 줄인다.
이분 탐색이 끝나면, left에 최소 시간이 저장되어 있다. (left가 조건이 안 맞을 때도 +1을 진행하니)

헤맨 지점

처음에는 한명을 심사하는데 걸리는 최대 시간이 10^9이니, 찾아야하는 범위가 1~10^9 라고 착각했다. 따라서 right의 초기값을 10^9로 했다가, 계속 틀리게 되었다. 하지만 (한명 검사 시간) * (사람의 수)가 최대 시간인 것을 파악하고 다시 수정했다.
이분 탐색은 탐색을 시작하는 최솟값, 최댓값, 그리고 반환하는 값을 한번에 파악할 수 있어야 빠르게 해결이 가능한 것 같다.