이분탐색 > 입국심사

https://www.welcomekakao.com/learn/courses/30/lessons/43238#

 

이 문제는 결국엔 다른사람의 답을 보고서 이해하여 짠 코드이고, 문제를 푸는 로직은 아래와 같다.

1. 이분 탐색을 하기위한 최솟값과 최댓값을 구해야한다. 문제에 보면 입국심사를 기다리는 인원은 1명이상, 심사관이 소모하는 시간은 1분이상이므로 최솟값은 1이다. 최댓값은 가장 오래걸리는 심사대에서 n명이 모두 심사를 받는 경우이다.

2. 특정 시간에서 몇명이 심사를 받을 수 있는 지 계산하면 된다. 이를 최솟값부터 최대값까지 그대로 계산한다면 O(N)의 시간이 걸리지만, 이분 탐색을 실시하면 O(logN) 에 정답을 찾을 수 있다.

3. 이분 탐색을 실시하면서
3-1. mid 값의 시간일 때, 몇명을 심사할 수 있는 지 계산한다. (16 line)
3-2. n명보다 같거나 많아진다면 answer 를 갱신한다. (19 line)
3-3. n명보다 같거나 많아진다면 최댓값을 줄여주고, 그게 아니라면 최솟값을 늘려주면 된다. (21~22 line)

이 문제에서 주의해야할 점은 아래와 같다.
11 line - 최댓값을 지정해줄 때 long long type 으로 변환을 해주어야 한다.
21 line - 특정 mid 시간에 대해 n명이상의 심사가 가능하다면 최댓값을 줄여주어야 한다.
예제 케이스 중 하나로 5, [1, 2] 를 실시하면 딱, 5명에 맞게 sum 이 도출되진 않는다.
답은 4분인 반면에 4/1 => 4, 4/2 => 2, 총 4분에 6명이 가능하게 되므로 이런 예외케이스도 고려해야 한다. 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
long long solution(int n, vector<int> times) {
    long long answer = 0;
    sort(times.begin(), times.end());
    
    long long left = 1;
    long long right = answer = (long long)times[times.size() - 1] * n;
    while (left <= right) {
        long long mid = (left + right) / 2;
        long long sum = 0;
        for (int i = 0; i < times.size(); ++i) {
            sum += mid / (long long)times[i];
        }
        
        if (sum >= n) answer = answer > mid ? mid : answer;
 
        if (sum >= n) right = mid - 1;
        else left = mid + 1;
    }
    
    return answer;
}