<Programmers>Binary Search_입국심사 c++

💡Summary & Idea

• times에는 심사관 한 명이 심사하는데 걸리는 시간이 담겨있다
• 입국 심사를 기다리는 사람은 n명이고, 범위는 1명이상 10^10이다
• 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 해야 한다
• times에 저장된 값을 오름차순 정렬을 하면 심사관 한 명이 심사하는데 걸리는 최소 시간은 1, 최대 시간은 times.back()이다.
• 모든 사람이 심사를 받는데 걸리는 시간의 최소는 1 (기다리는 사람 1명, 처리시간 1분일 때), 최대는 n*times.back()이다
• 이 범위에서 이진 탐색을 하며 시간을 줄여나간다

✏️Solution

• 최소, 최대 범위를 지정

long long low=1; 
long long high=n*(long long)times.back();
long long mid;

• mid 값을 정하고, 이 시간 내에 각 심사관이 처리할 수 있는 사람의 수를 센다

for (int i=0; i<times.size(); i++) 
	cnt+=mid/times[i];

• 처리할 수 있는 사람의 수가 n보다 크거나 같다면 answer=mid로 매번 갱신해주고 전체 범위를 줄여주기 위해 high=mid-1로 바꾸어준다
• 처리할 수 있는 사람의 수가 n보다 작다면 mid+1~high 범위에서 재탐색을 한다

if (cnt<n)
	low=mid+1;
else {
	answer=mid;
	high=mid-1;
}

Source Code

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

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    sort (times.begin(), times.end());
    long long low=1; 
    long long high=n*(long long)times.back();
    long long mid;
  
    while (low<=high) {
        mid=(low+high)/2;
        long long cnt=0;
        for (int i=0; i<times.size(); i++) 
            cnt+=mid/times[i];
     
        if (cnt<n)
            low=mid+1;
        else {
            answer=mid;
            high=mid-1;
        }
    }
    return answer;
}