[백준 알고리즘] 3079번: 입국심사

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

문제

문제

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

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

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

예를 들어, 두 심사대가 있고, 심사를 하는데 걸리는 시간이 각각 7초와 10초라고 하자. 줄에 서 있는 사람이 6명이라면, 가장 첫 두 사람은 즉시 심사를 받으러 가게 된다. 7초가 되었을 때, 첫 번째 심사대는 비어있게 되고, 세 번째 사람이 그곳으로 이동해서 심사를 받으면 된다. 10초가 되는 순간, 네 번째 사람이 이곳으로 이동해서 심사를 받으면 되고, 14초가 되었을 때는 다섯 번째 사람이 첫 번째 심사대로 이동해서 심사를 받으면 된다. 20초가 되었을 때, 두 번째 심사대가 비어있게 된다. 하지만, 여섯 번째 사람이 그 곳으로 이동하지 않고, 1초를 더 기다린 다음에 첫 번째 심사대로 이동해서 심사를 받으면, 모든 사람이 심사를 받는데 걸리는 시간이 28초가 된다. 만약, 마지막 사람이 1초를 더 기다리지않고, 첫 번째 심사대로 이동하지 않았다면, 모든 사람이 심사를 받는데 걸리는 시간이 30초가 되게 된다.

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

입력

첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

풀이

어떤 시간 T 동안 한 심사대에서 처리할 수 있는 사람들의 숫자를 구하는 것은 간단하다. T / 한 사람을 처리하는데 걸리는 시간 의 몫을 구하면 된다. 그렇다면 만약 7초 걸리는 심사대와 10초 걸리는 심사대가 있고, 시간 T가 30 이라면, 7초 걸리는 심사대 에서는 4명을 처리하고, 10초 걸리는 심사대에서는 3명을 처리하게 되어 총 7명을 처리할 수 있다는 것을 알아낼 수 있다.

위와 같은 특징을 이용해서 어떤 시간 T를 찾아야할 최소 시간으로 잡고 이분탐색을 진행하면, 최소 시간을 찾아낼 수 있을 것이다. 우리가 가지고 있는 정보는 각 심사대에서 걸리는 시간과 심사를 받아야하는 사람의 수이기 때문에 첫 이분 탐색에서는 초기값을 가장 왼쪽은 1, 가장 오른쪽은 가장 시간이 오래걸리는 심사대의 시간 * 사람 수로 잡을 수 있다. 이분 탐색을 진행하면서 만약 어떤 시간 T로 처리할 수 있는 사람의 수가 심사받아야 하는 사람의 수보다 작다면, 시간을 더 늘려야 한다는 것을 의미한다. 그래서 이 경우에는 head 를 mid + 1 로 만들어 범위를 더 큰 값으로 좁혀준다. 반대로 어떤 시간 T로 처리할 수 있는 사람의 수가 심사를 받아야하는 사람의 수보다 크다면, 시간을 더 줄여볼 수 있다는 것을 의미하기 때문에 이 경우에는 tail 을 mid - 1 로 만들어 범위를 더 작은 값으로 좁혀준다.

코드

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

using namespace std;

typedef long long ll;

vector<ll> times;

ll calcPeople(ll mid)
{
    ll sum = 0;
    for (auto time : times)
    {
        sum += (mid / time);
    }

    return sum;
}

ll binarySearch(ll head, ll tail, ll target)
{
    ll mid = 0;
    ll result = 0;
    while (head <= tail)
    {
        mid = (head + tail) / 2;
        ll maxPeople = calcPeople(mid);

        if (maxPeople >= target)
        {
            tail = mid - 1;
            result = mid;
        }
        else
        {
            head = mid + 1;
        }
    }
    return result;
}

int main()
{
    int N, M;
    cin >> N >> M;
    ll maxTime = 0;

    for (int i = 0; i < N; i++)
    {
        ll time;
        cin >> time;
        times.push_back(time);
        maxTime = max(maxTime, time);
    }

    cout << binarySearch(1, maxTime * M, M);
}