3079번: 입국심사 - 이분 탐색

https://www.acmicpc.net/problem/3079

3079번: 입국심사

 

관찰

N = 3, M = 6이라 하고, 주어진 \(T_{k}\)를 (1, 2, 4)라 하자. 이때 시간에 따른 심사받은 인원을 나열하면 다음과 같다.

시간	1	2	3	4	5	6	...
심사받은 수	1	3	4	7	8	10	...

심사받은 수를 배열이라 생각하면, 이 배열 내에서 M = 6보다 크거나 같은 최소의 심사받은 수를 찾아 그 시간을 알아내면 된다. 따라서 답은 4이다.

 

알고리즘

위의 관찰과 같은 방식은, 이분 탐색(lower_bound)와 완전히 동일하다. 따라서 이 문제는 이분 탐색으로 풀 수 있다.

 

구현

\(T_{k}\)의 최댓값이 \(10^{9}\)이고, M의 최댓값이 \(10^{9}\)이기에 모든 인원이 전부 심사받을 때까지 걸리는 최대 시간은, N = 1, M = \(10^{9}\), \(T_{1} = 10^{9}\)일 때의 최대 시간인 \(10^{18}\)이다. 심사받은 수를 배열로 구현해 lower_bound method를 쓰는 것은 불가능하기에, 직접 lower_bound를 구현해야 한다.

이분 탐색을 구현해 얻은 mid 값을 \(T_{k}\)로 나누면, 해당 심사대에서 mid 시간 동안 심사한 인원 수가 나오므로 이들을 모두 더해(sum) M과 비교하여 left, right를 조절하면 된다. 단, 이렇게 구현했을 경우 sum 값이 unsigned long long 범위를 넘어 overflow가 발생하므로 sum이 답이 될 수 있는 최댓값인 \(10^{18}\)을 넘어서면 break할 필요가 있다.

#include <bits/stdc++.h>
#define inf 1e9
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

ll N, M;
ll table[100001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N >> M;

    for (int i{1}; i <= N; i++)
        cin >> table[i];

    ll lef = 0, rig = 1e18;
    while (lef < rig)
    {
        ll mid = (lef + rig) / 2;
        ll sum = 0;

        for (int i{1}; i <= N; i++)
        {
            sum += mid / table[i];
            if (sum > 1e18)
                break;
        }

        if (sum < M)
            lef = mid + 1;
        else
            rig = mid;
    }
    cout << rig << "\n";
}