[백준] 3079번 입국심사 (C++)

문제 링크

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

3079번: 입국심사

 

문제 설명

입국심사대 N개에 대해 M명이 입국 심사를 받는다.

N과 M이 주어지며, 다음 N개의 줄에 각 심사대에서 심사를 하는 데 걸리는 시간이 주어진다.

최종적으로 심사를 마치는 데 걸리는 시간의 최솟값을 구한다.

 

사고 과정

백준에 제시된 예제를 활용하며 걸리는 시간에 대한 이분 탐색으로 문제를 해결해야겠다는 생각이 들었다.

예제 입력 2를 보면 답은 8이 되며, 7개의 입국심사대에서는 8분 동안

각각 2, 1, 2, 1, 0, 4, 2명이 입국심사를 받을 수 있으므로, 최대 12명이 입국심사를 받을 수 있다.

만약 7분이 주어진다면 최대 9명 (2+0+2+1+0+3+1)이 입국심사를 받을 수 있으므로 답이 될 수 없다.

 

변수 left을 1로, right를 M * (가장 긴 심사 시간)으로 설정하고,

이분 탐색을 통해 심사를 받을 수 있는 사람의 개수가 M이상인 경우의 최소 시간을 찾았다.

 

해결 방법

각 심사시간의 최댓값과 M의 최댓값을 고려했을 때 나올 수 있는

결괏값의 범위는 1~10의 18승 이므로 int가 아닌 long long을 활용하였다.

 

또한 cntPeople()이라는 함수를 활용하여, 해당 시간에 입국심사를 받을 수 있는 최대 인원을 계산하였다.

이는 인자로 입력받은 시간을 각 배열의 값들을 나누어 모두 합침으로써 계산하였다.

 

코드

#include <iostream>
#include <math.h>
#include <algorithm>

using namespace std;
typedef long long ll;

int M, N;
ll MAX;
ll arr[100001];

void init();
void input();
ll cntPeople(ll num);
void solve();

void init()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    MAX = 0;
}

void input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
        MAX = max(arr[i], MAX);
    }
}

ll cntPeople(ll num)
{
    ll cnt = 0;

    for (int i = 0; i < N; i++)
    {
        cnt += num / arr[i];
    }
    return cnt;
}

void solve()
{
    ll left = 1;
    ll right = MAX * M;
    ll mid, cnt;

    ll result = 0;

    while (left <= right)
    {
        mid = (left + right) / 2;
        cnt = cntPeople(mid);

        if (cnt < M)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
            result = mid;
        }
    }
    cout << result;
}

int main()
{
    init();
    input();
    solve();
    return 0;
}