[Programmers] 이분탐색 > 입국심사(c++)

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

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

 

이분탐색의 기준을 "시간"으로 설정했다.

start의 초깃값은 심사관을 기다리지않고 한번에 통과 했을때의 시간이고,

end의 초깃값은 가장 늦은 심사관을 모두 통과했을때의 시간이다.

 

1. mid는 start와 end의 평균값으로 설정

2. 현재 mid시간에서 통과할 수 있는 인원의 수를 person변수에 누적

3. 인원 수가 통과할 수 있는 인원수(=person) n보다 많으면 end범위를 mid - 1만큼 줄임

4. 인원 수가 통과할 수 있는 인원수 n보다 많으면 start범위를 mid + 1 만큼 늘림

5. start > end일때 반복문 종료, answer은 현재 start의 값 출력

 

#include <vector>
#include <string>
#include <algorithm>
using namespace std;
long long solution(int n, vector<int> times) {
    long long answer = 0;
    
    long long start = 1;
    long long end = (long long)*max_element(times.begin(), times.end())*(long long) n;
    long long mid;
    
    while (start <= end) {
        long long person = 0;
        mid = (start+end)/2;
        
        for(int i=0;i<times.size();i++) person += mid / times[i];
        
        if(n <= person) {
            end = mid - 1;
        }
        else if(n > person){
            start = mid + 1;
        }
        answer = start;
    }
     return answer;
}