https://programmers.co.kr/learn/courses/30/lessons/43238
코딩테스트 연습 - 입국심사
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한
programmers.co.kr
입국 심사
이 문제는 이분탐색 카테고리에 해당하는 문제입니다.
또한 숫자의 범위가 굉장히 크기 때문에 int가 아닌 long long을 사용해야함을 기억해야합니다.
심사원들의 입국심사 시간이 주어졌을 때, 최소한의 시간에 주어진 인원이 모두 심사를 받을 수 있는 시간을 찾아야합니다.
그렇다면 시간의 범위를 설정해야합니다. 시간은 1초부터 최악의 시간을 초기 범위로 설정합니다.위 문제에서 최악의 시간은, 소요시간이 가장 긴 입국 심사원한테 n명이 심사를 받는 경우 입니다.
가장 먼저 주어진 times를 정렬시켜줍니다.
정렬 후 가장 큰 값(times[times.size()-1])을 tmp로 저장합니다.
hi = tmp * n로 설정하여 최대 범위를 설정합니다.
mid= (lo+hi)/2로 설정합니다.
이제 mid 분 안에 최대 몇명이 심사를 통과할 수 있는지 계산하면 됩니다.
계산 방법은 ret += mid/times[i]입니다.
ret에 times를 모두 돌면서 해당 연산의 결과 값을 더해줍니다.
그리고 ret > n 이라면 hi = mid -1로 변경 후 반복문을 돌려줍니다.
그 외의 경우는 lo = mid+1로 변경 후 반복문을 돌려줍니다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
long long BinarySearch(long long mid, vector<int> T){
long long ret =0;
for(int i=0;i<T.size();i++){
ret = ret + (mid / T[i]);
}
return ret;
}
long long solution(int n, vector<int> times) {
long long tmp =0;
sort(times.begin(), times.end());
tmp = times[times.size()-1];
long long lo = 0;
long long hi = tmp * n;
long long mid;
while(lo <= hi){
mid = (lo+hi)/2;
if(BinarySearch(mid, times) < n) lo = mid+1;
else hi= mid-1;
}
return lo;
}