🔍 3079 입국심사

상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다.

가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다. 하지만 항상 이동을 해야 하는 것은 아니다. 더 빠른 심사대의 심사가 끝나길 기다린 다음에 그 곳으로 가서 심사를 받아도 된다.

상근이와 친구들은 모두 컴퓨터 공학과 학생이기 때문에, 어떻게 심사를 받으면 모든 사람이 심사를 받는데 걸리는 시간이 최소가 될지 궁금해졌다.

상근이와 친구들이 심사를 받는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

---

🤔 풀이

• 일정한 시간(mid)동안 한 심사대가 처리할 수 있는 사람의 수(cnt_sub)를 구하고 해당 인원 수를 모든 심사대에 걸쳐 더한 값이 상근이와 친구들의 수보다 작다면 시간을 늘리도록 이분탐색을 진행하여 구한다.
• 걸리는 시간의 최솟값을 구해야 하기 때문에 lower bound를 구한다.
• 일정한 시간을 심사대가 한 사람을 처리하는데 걸리는 시간으로 나누면, 심사대가 처리 가능한 인원수가 나온다. 처리 시간이 짧은 순으로 심사대를 정렬한 다음 차례차례 정해진 시간 안에 심사대가 처리할 수 있는 인원수를 구한다. 만약 모든 심사대를 거쳐도 남아 있는 인원이 0명보다 많다면 정해진 시간을 늘려서 수용 가능하도록 해야한다. 남아 있는 인원이 0명 이하라면 시간을 줄이는 방향으로 최솟값을 구한다.

---

📝 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int N, M;
    cin >> N >> M;
    vector<int> time(N);
    for (int i = 0; i < N; i++) {
        cin >> time[i];
    }
    sort(time.begin(), time.end());

    long long low = 0, high = (long long)time[N-1]*M + 1;    

    while (low < high) {
        long long mid = (low+high)/2;
        long long remain_people = M;
        
        for (int i = 0; i < N; i++) {
            remain_people -= mid/time[i];
            if (remain_people <= 0) break;
        }

        if (remain_people <= 0) { // 시간을 더 줄여야함...
            high = mid;
        }
        else {  // 시간을 더 늘리는 경우
            low = mid+1;
        }
    }

    cout << low;

    return 0;
}