[C++] 프로그래머스 입국심사

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

프로그래머스

풀이

각 심사관이 한 사람을 심사하는데 걸리는 시간을 알 때, 모든 사람(n)을 심사하는데 걸리는 시간을 최소화 하고 싶다.

이분 탐색을 활용해서 간단히 답을 찾을 수 있다.

1. 정답(최소 시간)을 가정하여, 해당 시간 동안 심사관이 각각 검사할 수 있는 입국자 수를 카운트한다.

2. 카운트 한 값이 입국자 수보다 작다면 시간이 부족하다는 뜻이므로 start = mid+1 이다.

3. 반대로 카운트 한 값이 입국자 수보다 크다면 시간이 많았다는 뜻이므로 end = mid-1이다.

#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 start = 1; // minimum time
    long long end = (long long) times[times.size()-1] * n; // maximum time
    while (start <= end) {
        long long mid = (start  + end) /2; // 정답을 가정
        long long cnt = 0;
        // 가정한 시간 동안 심사할 수 있는 사람 수는?
        for (int i = 0; i < times.size(); i++) {
            cnt += mid / times[i];
        }
        
        if (cnt < n)
            start = mid + 1;
        else {
            if (mid <= end)
                answer = mid;
            end = mid - 1;
        }
    }

    return answer;
}