백준 3079 입국심사

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

 

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


using namespace std;

vector<long long> arr;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;

    cin >> n >> m;

    arr.resize(n);


    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    sort(arr.begin(), arr.end());

    long long l = 1;
    long long r = arr.back() * m;

    while (l <= r) {

        long long mid = (l + r) / 2;
        long long cnt = 0;

        for (int i = 0; i < n; i++) {
            cnt += mid / arr[i];
            if (cnt > m) {
                break;
            }
        }

        if (cnt < m) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }

    }

    cout << l;


    return 0;
}

 

 이분 탐색 문제이다.

 n 개의 심사대에서 m명이 심사를 받는 데 걸리는 시간의 최솟값을 구하는 문제이다.

 

풀이

다음의 입력이 주어졌다고 가정하자.

2 6
7
10

 

해당 심사를 받는 데 걸리는 시간은 1부터 6명이 모두 상담에 10이 걸리는 상담소에서 받는 60까지에 있다. 이 범위를 가지고 이분 탐색을 실시한다.

        long long mid = (l + r) / 2;
        long long cnt = 0;

        for (int i = 0; i < n; i++) {
            cnt += mid / arr[i];
            if (cnt > m) {
                break;
            }
        }

  해당 시간의 중간값에 대하여 사람 수를 계산한다. (총 상담 시간)=(상담 대상 인원)*(각 상담에 걸리는 시간)이므로 이항하여 구할 수 있다. 오버플로우가 날 수 있으니 해당 시간에 상담 인원을 넘어갔을 경우 반복문을 종료한다.

        if (cnt < m) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }

 이후 cnt가 상담 인원보다 작을 경우 상담 시간을 늘려야 하고, 반대의 경우 줄여야 한다. 해당 이분탐색을 통해 상담시간을 구하여 출력하면 정답을 구할 수 있다.