프로그래머스 입국심사 - C++

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

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

using namespace std;
long long left, right, mid, allTime;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    sort(times.begin(), times.end());
    
    left = 1;
    right = (long long) times[times.size() - 1] * n;
    
    while(left <= right){
        mid = (left + right) / 2;
        
        allTime = 0;
        
        for(int i = 0; i < times.size(); i++)
            allTime += mid / times[i];
        
        // 시간 부족
        if(allTime < n)
            left = mid + 1;
        else { // 시간 충분
            answer = mid;
            right = mid - 1;
        }
    }
    
    return answer;
}

---

뭔가 어떻게 이진탐색을 해야하지 고민이 되는 문제였습니다. 범위만 잘 잡는다면 금방 풀 수 있습니다.

1. 이진탐색의 left는 최소로 잡기 위해 1로 설정
2. right의 경우 나올 수 있는 최고의 경우,
즉 [제일 오래 걸리는 검사관 X 사람 수]

 위 조건대로 left와 right를 설정해준다면 이후는 평소의 이진탐색대로 할 수 있으며 마지막에 나오는 mid 가 answer가 됩니다