[프로그래머스 lv3] 입국심사 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

이분탐색의 대표적인 유형으로, 소요 시간의 탐색 범위를 반으로 줄여 나가면서 n명의 줄서기가 가능한 최소 소요시간을 log(n)에 구하는 문제이다.

탐색 범위의 시작을 first, 탐색 범위의 마지막을 last라 했을 때, 주어진 시간이 mid = (first+last)/2 이면 n명의 사람이 모두 입국심사를 받을 수 있는지 확인한다. 만약, 가능하다면 일단 최소 시간을 mid로 기록하고, 탐색 시간의 끝을 last = mid-1로 조정한다. 만약, 가능하지 않다면 최소 시간의 탐색 범위를 first = mid+1로 조정한다.

 

n명의 사람이 모두 mid 시간 내에 입국심사를 받을 수 있는지 확인하기 위해서는, 각 입국심사대에서 mid 시간에 몇명의 심사를 진행할 수 있는지(mid/times[i])를 구해 모두 더한 값을 보면 된다. 만약, 각 입국심사대에서 mid 시간동안 심사할 수 있는 사람의 총 합이 n이상이라면 mid 시간은 최솟값의 후보가 될 수 있다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using l = long long;

bool check(l limits, l n, const vector<int>& times) {

    l t = 0;
    for (int i=0; i<times.size(); i++) 
        t += limits/(1LL*times[i]);
    return t >= n;
}

l binarySearch(l n, const vector<int>& times) {

    l first = 1;
    l last = (*min_element(times.begin(), times.end()))*n;
    l ret = last;

    while (first <= last) {
        l mid = (first+last)/2;
        if (check(mid, n, times)) {
            ret = mid;
            last = mid-1;
        }
        else first = mid+1;
    }
    return ret;
}

long long solution(int n, vector<int> times) {

    return binarySearch(n, times);
}