Level 3. 입국심사

Level 3. 입국심사

 

 

도저히 이 문제가 왜 이분 탐색 문제인지 감이 안 잡혀서 찾아보았다.

• 이분 탐색 문제는 입력의 크기가 매우 큰데 하나의 답을 찾아야 하는 것이 특징이다.

 

포인트는 사람 수가 아닌, 시간을 중심으로 이분 탐색을 진행해 답을 찾는다는 것이었다.

• 가장 오래 걸리는 심사관에게 모두 심사를 받는 경우를 최악의 경우로 설정한다.

 

이분 탐색을 진행할 때마다 주어진 시간 동안 모든 사람이 심사를 받을 수 있는지 확인한다.

• 각 (주어진 시간 / 심사 시간)을 합한 값이 심사할 수 있는 사람의 수라는데 처음엔 왜 이렇게 되는지 이해가 되지 않았다.
• 하지만, 사람이 아니라 각 심사관을 중심으로 생각해보면 실제로 그렇다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> times)
{
    long long s = times.front();
    long long e = (long long) * max_element(times.begin(), times.end()) * n;

    while (s <= e)
    {
        long long nPeople = 0;
        long long m = (s + e) / 2;

        for (int tm : times)
            nPeople += (m / tm);

        if (nPeople < n)
            s = m + 1;
        else
            e = m - 1;
    }

    return ++e;
}