[프로그래머스/C++] 입국심사

1. 개요

https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

1-1. 설명

n명이 입국 심사를 위해 줄을 서서 기다리고 있다. 각 입국 심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다르다. 처음 시작 시, 모든 심사대는 비어있으며, 한 심사대에 한 명만 심사가 가능하다. 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하는 함수를 구현한다. 

1-2. 제한 사항

 - 입국 심사를 기다리는 사람 수 n은 1 이상 1,000,000,000 이하 자연수

 - 각 심사관이 한명을 심사하는데 걸리는 시간 배열은 times, 한 명을 심사하는데 걸리는 시간은 1 이상 1,000,000,000 이하 자연수

 - 심사관은 1 이상 100,000 이하

---

2.구현

2-1. 풀이

이분 탐색 문제이나, 기준을 어디서 둬야할 지 살짝 헤맸었다. times를 기준으로 두지말고 [1 ~ 모두 검사하는데 걸리는 최대시간]을 기준으로 이분 탐색을 진행하며 n명 이상이 걸리는 시간의 최솟값을 반환하면 된다.

2-2. 코드

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

using namespace std;

long long minimumTime;
long long BinarySearch(long long first, long long last, int n, vector<int> times);

long long solution(int n, vector<int> times) {
    minimumTime = 0;
    sort(times.begin(), times.end());
    long long answer = BinarySearch(1, n * (long long) times.back(), n, times);
    return answer;
}

long long BinarySearch(long long first, long long last, int n, vector<int> times){
    if (first > last) return minimumTime;
    long long mid = (first + last) / 2;
    // mid : 심사를 받는데 걸리는 시간
    long long count = 0;
    for (long long time : times) count += (mid / time);
    // mid 시간 기준 몇 명의 인원이 처리되었는지 확인
    if (count >= n) {
        minimumTime = mid;
        return BinarySearch(first, mid - 1, n, times);
    }
    else return BinarySearch(mid + 1, last, n, times);
}