입국심사(이분 탐색)

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

프로그래머스

 

이번 이분탐색 문제도 헤매다가 결국 힌트를 보고 깨달았는데...

 

심사 받는 사람의 수를 탐색하는 것이 아닌 소요되는 시간을 이분탐색으로 최대한 줄여나가면 된다.

이전에 풀었던 공유기 설치 문제와 동일한 방법이다.

https://djgameprogramming.tistory.com/117

공유기 설치(이분 탐색, 그리디)

 

최소 소요 시간을 1, 최대 소요 시간을 가장 오래 걸리는 심사관에게 모두 심사받는 시간으로 설정한다.

이 최솟값과 최댓값의 중간값을 구하여 해당 시간이 소요되었다고 할때 각 심사관마다 심사할 수 있는 사람의 수를 구한다.

이렇게 구한 사람의 수와 심사 받아야 할 사람의 수를 비교하여 이분탐색으로 중간값을 최대한 줄여나간다.

 

이분탐색 과정에서 무한루프에 빠지지 않도록 조건의 설정에 유의하도록 한다.

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long binary_search(long long front, long long end, int n, vector<int> times)
{
    int ret = 0;
    while (front < end)
    {
        long long mid = (front + end) / 2;
        long long count = 0;
        for (int time : times)
        {
            count += mid / (long long)time;
        }
        if (n <= count)
        {
            end = mid;
        }
        else
        {
            front = mid + 1;
        }
    }
    return front;
}

long long solution(int n, vector<int> times)
{
    sort(times.begin(), times.end());
    long long max = (long long)times[times.size() - 1] * n;
    long long answer = binary_search(1, max, n, times);
    return answer;
}