🚀 [입국심사] Lv. 3 문제
이분법을 사용하여 시간이 주어질 때 모든 인원이 입국심사를 끝낼 수 있는지로 푼다. 코드참고
💎 전체 코드는 다음과 같습니다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int N;
vector<int> Times;
// 시간 time 안에 모두 심사가 가능하면 true 아니면 false;
bool finish(long long time){
// 시간이 주어질때 통과할 수 있는 심사자의 수.
long long total= 0;
for(int i =0; i < Times.size(); i++){
total += time / Times[i];
}
if(total >= N){
return true;
}
return false;
}
long long solve(){
long long lo = 0, hi = 1e18 // 사람최대수(1e9) * 심사하는대걸리는최대시간(1e9) ;
while(lo + 1 < hi){
long long mid = (lo+hi)/2;
if(finish(mid)){
hi = mid;
}
else{
lo = mid;
}
}
return hi;
}
long long solution(int n, vector<int> times) {
long long answer = 0;
N = n;
Times = times;
sort(Times.begin(), Times.end());
answer = solve();
return answer;
}
Comments