문제 조건

input

• 입국 대기자 n
  • 1 ≤ n ≤ 1,000,000,000
• 각 심사관의 심사 시간을 기록한 vector times
  • 1 ≤ times ≤ 100,000

output

• 입국 심사를 완료할 수 있는 최소 시간

문제 해석

풀이 전략

1. 이진 탐색
   1. s를 최소 시간 1, e를 최대 시간 n * times.max()
   2. 이진 탐색으로 입국 심사가 가능한지 판단
      1. 가능하다면, e=mid
      2. 불가능하다면, s=mid+1

코드

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

using namespace std;

long long solution(int n, vector<int> times) {
    sort(times.begin(), times.end());
    long long s = 1;
    long long e = n * (long long)times.back();
    
    while (s < e) {
        long long mid = (s+e) / 2;
        long long passed = 0;
        
        // mid라는 시간 동안 최대 몇명 심사 가능한지 판단
        for (auto time : times) {
            passed += mid / (long long)time;
        }
        
        if (passed >= n) {
            e=mid;
        } else {
            s=mid+1;
        }
    }
    
    return s;
}