프로그래머스 - 입국심사

프로그래머스 - 입국심사

이분탐색 문제로 최소로 걸리는 시간을 구해야하기 때문에
걸리는 시간을 이분탐색의 주체로 잡는다.

left를 1로 right를 충분히 큰 숫자로 (입국 심사를 기다리는 사람의 숫자와 걸리는 시간의 최대 값이 1 << 30 보다 작아서 이 둘을 곱한 1L << 60 정도로 잡았다) 설정한다.

만약 n = 6, times = [7, 10] 일 때, left = 1, right = 39이고 mid = (left + right)/2 = 20을 현재 시각이라고 생각하면 7분씩 걸리는 심사관은 2번, 10분씩 걸리는 심사관은 2번이므로 총 4번 가능하다. 이는 n = 6보다 작다.
즉, 오른쪽을 탐색해야 하므로 left를 21로 right를 39로 설정하고 mid = 30일 때로 다시 계산한다.
30일 경우엔 (30 / 7) = 4, (30 / 10) = 3 으로 4 + 3 = 7 이고 이는 n = 6보다 크기 때문에 left를 21, right를 29로 다시 설정하고 한다.
이를 left <= right 일 때 까지만 하면 된다.

코드는 아래와 같다.

#include <string>
#include <vector>

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    
    long long left = 1;
    long long right = (long long)(1L << 60);
    long long mid;
    answer = right;
    
    while(left <= right) {
        mid = (left + right) / 2;
        
        long long check_cnt = 0;
        for(int i=0;i<times.size();i++) 
            check_cnt += (long long)(mid / times[i]);
        
        if(check_cnt < n) 
            left = mid + 1;
        else {
            right = mid - 1;
            answer = min(mid, answer);
        }
    }
    
    return answer;
}