[프로그래머스] 입국심사 (Lv.3) c++

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

코딩테스트 연습 - 입국심사

 

입국 심사

이 문제는 이분탐색 카테고리에 해당하는 문제입니다.

또한 숫자의 범위가 굉장히 크기 때문에 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;
}