[Algorithm] Programmers :: 입국심사

https://school.programmers.co.kr/learn/courses/30/lessons/43238?language=cpp 

프로그래머스

long long solution(int n, vector<int> times) {
    long long answer = 0;
 
    sort(times.begin(), times.end());
    long long left = 1;
    long long right = (long long)times[times.size() - 1] * n;
 
    while (left <= right)
    {
        long long mid = (left + right) / 2;
 
        long long count = 0;
 
        for (int i = 0; i < times.size(); ++i)
        {
            count += mid / times[i];
        }
 
        if (count >= n)
        {
            answer = mid;
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
 
    return answer;
}

애초에 카테고리가 이분탐색이라서 대략적으로 어떤식으로 접근해야할지는 알 수 있었다.

'시간'을 이분탐색으로 조절해가며, 해당시간 내에 전부 입국심사가 가능한지에 대해 Yes or No를 구하면 된다.

 

left값과 right값은 문제의 조건에 맞춰서 설정한다.

이 문제에서 나올 수 있는 최소시간은 사람 1명, 심사관이 심사하는데 걸리는 시간 1분인 경우이기 때문에 1*1인 1이다.(left값) 즉 최소 인원수 * 최소 심사시간

 

최대값은 그 반대로 최대인원수 * 최대 심사시간이다.

그렇기 때문에 먼저 times를 오름차순으로 정렬 후, n(최대인원수) * times[times.size()-1] (최대심사시간) 으로 구해주면 된다. (right 값)

 

left값과 right값을 설정했으니 이후 Yes or No에 따라 범위를 조절하면 된다.

해당부분은 times를 순회하며 mid(시간)을 각 심사대의 심사시간(times[i])을 나눈 몫을 합산한 후,

n명이상인지에 대한 여부로 Yes or No를 가린다.