입국심사 [Lv. 3]

프로그래머스

입국 심사를 기다리는 n명의 사람이 있고, 여러 심사관이 있습니다. 각 심사관들의 심사 시간을 times 배열로 입력 받을 때 6명의 사람을 입국 심사하는데 걸리는 최소 시간을 구하시오.

 

ex) 6명의 대기자가 있고 times = [7, 10] 일 때 최소시간 28분 소요됨

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

 

풀이 방법

이진 탐색을 이용하면 쉽게 해결할 수 있습니다.

1. 이진 탐색의 범위 설정:
   • 최소 시간: 1분
   • 최대 시간: 가장 느린 심사관이 N명을 모두 처리하는 경우가 가장 긴 시간이므로 최대 시간 = 가장 느린 심사관의 처리 시간 * N명.
2. 이진 탐색을 통해 최소 시간 구하기: 이진 탐색을 통해, 주어진 중간 시간(mid)에 각 심사관이 처리할 수 있는 인원수를 계산한 후, 그 인원수가 N명 이상이 되는지를 판단합니다.
   • 각 심사관이 mid 시간 동안 처리할 수 있는 인원은 mid // 각 심사관의 처리 시간입니다.
   • 모든 심사관이 처리한 인원을 합산하여, 그 수가 N명 이상이라면 주어진 시간이 충분하다는 의미이므로 시간을 더 줄여도 됩니다. 반면, N명보다 적다면 시간이 부족하다는 의미이므로 시간을 늘려야 합니다.
3. 구체적인 풀이 과정:
   • start = 1, end= 가장 느린 심사관의 처리 시간 * N
   • mid = (start+ end) / 2
   • 각 심사관이 mid 시간 동안 처리할 수 있는 인원의 총합을 계산한 후, 이 값이 N 이상인지 확인합니다.
   • N 이상이면, end값을 mid - 1로 줄여서 더 짧은 시간을 탐색하고, N 미만이면 start값을 mid + 1로 설정하여 더 긴 시간을 탐색합니다.
4. 종료 조건: 이진 탐색이 종료된 후, 최종적으로 start 값이 N명이 모두 심사를 받을 수 있는 최소 시간을 의미하게 됩니다.

 

정답 코드 

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

using namespace std;

long long solution(int n, vector<int> times) {

    long long answer = 0;
    
    sort(times.begin(), times.end());
    long long start = 1;
    long long end = (long long)times.back() * n;
    
    while (start <= end)
    {
        long long mid = (start + end) / 2;
        
        long long cnt = 0;
        for (int time : times)
            cnt += mid / (long long)time;
    
        if (cnt < n)
            start = mid + 1;
        else{
            end = mid - 1;            
        }
    }
    
    return start;
}