[3079] 입국심사(C++)

문제

바로가기

상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다.

입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다.

가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다.

한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다. 하지만 항상 이동을 해야 하는 것은 아니다. 더 빠른 심사대의 심사가 끝나길 기다린 다음에 그 곳으로 가서 심사를 받아도 된다.

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

예를 들어, 두 심사대가 있고, 심사를 하는데 걸리는 시간이 각각 7초와 10초라고 하자. 줄에 서 있는 사람이 6명이라면, 가장 첫 두 사람은 즉시 심사를 받으러 가게 된다.

7초가 되었을 때, 첫 번째 심사대는 비어있게 되고, 세 번째 사람이 그곳으로 이동해서 심사를 받으면 된다.

10초가 되는 순간, 네 번째 사람이 이곳으로 이동해서 심사를 받으면 되고, 14초가 되었을 때는 다섯 번째 사람이 첫 번째 심사대로 이동해서 심사를 받으면 된다.

20초가 되었을 때, 두 번째 심사대가 비어있게 된다. 하지만, 여섯 번째 사람이 그 곳으로 이동하지 않고, 1초를 더 기다린 다음에 첫 번째 심사대로 이동해서 심사를 받으면, 모든 사람이 심사를 받는데 걸리는 시간이 28초가 된다.

만약, 마지막 사람이 1초를 더 기다리지않고, 첫 번째 심사대로 이동하지 않았다면, 모든 사람이 심사를 받는데 걸리는 시간이 30초가 되게 된다.

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

 

 

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000)

다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 $T_k$가 주어진다. (1 ≤ $T_k$ ≤ $10^9$)

 

 

출력

첫째 줄에 상근이와 친구들이 심사를 마치는데 걸리는 시간의 최솟값을 출력한다.

 

 

해결 방법

문제 설명처럼 심사대가 비어있을 때마다 다음 사람을 바로 이동시킬지, 기다렸다가 이동시킬지 결정하려면 생각만 해도 머리가 아프다.

애초에 사람의 수도 최대 1억명이기 때문에 logN에 문제를 해결해야 하고, 그러려면 이분 탐색을 사용해야 한다.

 

그럼 무엇을 기준으로 이분 탐색을 돌려야될까?

이 문제에서는 상근이와 친구들의 모든 심사가 끝나는 시간을 기준으로 이분 탐색을 돌려야 한다.

임의의 시간 동안 상근이와 친구들의 심사를 모두 끝낼 수 있는지 체크한 후, 만약 불가능하다면 시간을 좀 더 늘리고, 가능하다면 더 짧은 시간에도 커버가 가능한지 체크해야 한다.

 

문제의 예시로 생각해보면 초기의 left = 0, right = 60이고 mid = 30이 된다.

30초라는 시간동안 7초짜리 심사대는 30/7 = 4명을 커버할 수 있고, 10초짜리 심사대는 30/10 = 3명을 커버할 수 있다.

총 7명을 커버할 수 있으므로 더 짧은 시간에도 가능한지 체크하기 위해 right = mid - 1로 업데이트 한다.

그럼 left = 0, right = 29, mid = 14가 되고 14초 동안 두 개의 심사대에서 커버 가능한 인원은 각각 (14/7 = 2) + (14/10 = 1) = 3이므로 시간을 더 넉넉하게 만들기 위해 left = mid +1로 업데이트 한다.

left <= right일 때까지 이 과정을 반복하고 답을 출력하면 끝~!

 

 

내 코드

// [3079] 입국 심사
// 이분 탐색
#include <iostream>
using namespace std;

long long n, m, maxTime, t[100001];

void input()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> t[i];
        maxTime = max(maxTime, t[i]);
    }
}

void solve()
{
    long long left = 0, right = maxTime * m, ans;

    while(left <= right) {
        long long mid = (left + right) / 2;
        long long possiblePeople = 0; // mid초 동안 심사 가능한 인원

        for(int i = 0; i < n; i++) {
            possiblePeople += mid / t[i];
        }
        if(possiblePeople >= m) {
            right = mid - 1;
            ans = mid;
        }
        else {
            left = mid + 1;
        }
    }
    cout << ans << '\n';
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    input();
    solve();

    return 0;
}

Illustration Designed By denayunelp From LovePik.com