프로그래머스 Level3_ 입국심사 (C++)

이분탐색 문제이다. 

심사관이 맡을 수 있는 사람의 수 += 걸리는 추청 시간 / 심사관이 심사하는데 걸리는 시간

이 공식을 알아야지 문제를 풀 수 있다.

사람의 수가 많거나 같다면 최저시간을 저장한 후 추정시간을 늘리고 적다면 추정시간을 줄여본다.

 

#include <string>   // Level3_ 입국심사 [이분탐색]
#include <vector>
#include <algorithm>

#include <iostream>
using namespace std;

long long solution(int n, vector<int> times) {
    sort(times.begin(), times.end());
    long long l=0, r = (long long)(times[times.size()-1]) * n;
    long long answer = r;

    while(l<=r){
        long long mid= (l+r)/2;
        long long size = 0;
        for(int i = 0; i<times.size(); i++){
            size += mid / times[i];
        }
        if(size < n) l = mid+1;
        if(size >= n) {
            if(mid < answer)
                answer = mid;
            r = mid-1;

        } 
    }

    return answer;
}


// 입출력
int main(){
    int n, n_t;
    vector<int> times; 

    cin >> n >> n_t;

    for(int i=0;i<n_t; i++){
        int k;
        cin >> k;
        times.push_back(k);
    }

    cout << solution(n, times);
}