[프로그래머스/C++] 입국심사

✅ LV.3

📌 이분탐색

✏️ 최종 솔루션

⭐️ 이분 탐색 대상: 모든 사람을 입국 심사하는 데 걸리는 시간

1. left = 0, right = 최대 입국 심사 시간 * n
2. 각 심사대에서 시간 내에 심사할 수 있는 사람을 count 하기 위해 모든 입국 심사 시간을 돌면서 mid / 각 심사 시간 의 결과를 count
3. count 결과가 n 보다 크거나 같으면, 시간을 더 줄일 수 있다는 것이므로 answer 갱신하고 right 를 mid 이후 범위로 이동
   그렇지 않으면, left 를 mid 이전 범위로 이동

📌 self feedback

이분탐색 문제임을 파악하기가 어려웠음
시간 내애 심사할 수 있는 총 인원을 count 하기 위해 mid 를 심사시간으로 나눈 합을 구하는 방식을 도출하기 어려웠음

❗️ long long 형과 int 형을 계산할 때는, int 형을 long long 형과 연산하는 과정에서 int 범위를 넘어설 수 있기 때문에 int 형을 long long 형으로 변환해줘야 함

✏️ 최종 code

#include <iostream>
#include <vector>

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    long long left=0,right=(long long)times.back()*n;
    
    while(left<=right) {
        long long mid=(left+right)/2;
        
        long long cnt=0;
        for(int i=0;i<times.size();i++) {
            cnt+=(mid/(long long)times[i]);
        }

        if(cnt>=n) {
            answer=mid;
            right=mid-1;
        }
        else {
            left=mid+1;
        }
    }
    
    return answer;
}