[Baekjoon] 입국심사

👀 문제 설명

문제

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

 

입출력 예

 

✍🏻풀이

이분 탐색으로 푸는 문제인데, 아무리 생각해도 start와 end값, mid 값을 어떤 기준으로 정해야할지 모르겠다..!

검색해보니, 모든 사람이 심사를 받는데 걸리는 최소 시간을 구하는 문제이기 때문에, start와 end값도 시간을 생각하고 정하면 된다!

 

처음 시작할 때, start는 가장 최솟값이므로, 기다리는 사람의 수가 1이고, 심사 시간이 1분만 걸리는 심사관밖에 없을 때를 생각하고, 1로 둔다.

end는 시간을 기준으로 심사 시간이 가장 오래 걸리는 심사위원에게 n명 모두 갔을 때이므로, times.at(times.size() - 1) * n이다.

 

-- 이분 탐색 --

count 변수가 answer가 될 수 있는 값인데, count 변수는 시간이 아닌! mid 시간동안 심사할 수 있는 모든 사람의 수를 의미한다.

예를 들어, 1번 심사대가 한 명을 심사하는데 걸리는 시간을 5라고 한다면, 20이라는 시간동안 해당 심사대가 심사할 수 있는 사람의 수는 4명이다. 이 공식을 갖고 count 변수는 각 심사대가 mid 시간동안 심사할 수 있는 사람 수의 합이라고 두면 된다.

그리고, count 변수와 n 값을 비교한다.

count 값이 n보다 작으면, mid 라는 시간은 답이 될 수 없기 때문에, 더 큰 시간을 구해야 한다. 그러므로, start 값을 mid + 1로 바꿔준다.

count 값이 n보다 크면, mid 라는 시간은 답이 될 수 있고, answer에 mid값을 대입한다. 하지만 더 최솟값을 찾기 위해 end값을 mid - 1로 바꾸고, 다시 적합한 mid 값을 찾으면 된다.

 

위 이분 탐색을 start가 end 값보다 작거나 같을 동안 수행하면 된다.

 

[참고]

https://hochoon-dev.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%9E%85%EA%B5%AD%EC%8B%AC%EC%82%AC-c

https://yabmoons.tistory.com/521

 

코드

//  입국심사 (https://programmers.co.kr/learn/courses/30/lessons/43238)

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

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;

    // 일단 times를 정렬
    sort(times.begin(), times.end());
    // 시간을 기준으로 이분검색
    long long start = 1; // start 값은 제일 최소로 걸리는 시간인 1
    long long end = (long long) times.at(times.size() - 1) * n; // end 값은 주어진 심사대 중, 심사하는 데 가장 오래 걸리는 심사대의 시간 * n (모든 사람이 제일 오래 걸리는 심사대로 갈 경우)
    long long mid; // 이분 탐색의 기준

    while (start <= end) {
        // 탐색값 = 중앙값
        mid = (start + end) / 2;
    
        long long cnt = 0; // mid 시간동안 심사할 수 있는 모든 사람의 수

        for (int i = 0; i < times.size(); i++) {
            cnt += mid / times.at(i); // 각 심사대가 mid 시간동안 처리할 수 있는 사람들의 수를 더해준다.
        }

        if (cnt < n) { // n명 처리해야 하는데 cnt가 n보다 작다면, mid 시간동안은 처리할 수 없다는 뜻
            // 최솟값을 mid + 1로 좁힌다.
            start = mid + 1;
        }
        else { // mid 시간동안 n명의 사람을 처리하는데 충분하다는 뜻
            if (mid <= end) { // mid(기준 시간) 값이 end(최대 시간) 값보다 작다면,
                // mid는 최솟값이 될 수도 있기 때문에 answer에 넣는다.
                answer = mid;
            }
            // 최소 시간을 찾기 위해 범위를 더 좁힌다.
            end = mid - 1;
        }
    }

    return answer;
}

int main() {
    cout << solution(6, { 7, 10 }) << "\n";

    return 0;
}