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

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

문제 링크

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
long long solution(int n, vector<int> times) {

    sort(times.begin(), times.end()); // 안해도 됨(입력에서 이미 정렬되어 있는듯)
    long long N = n;
    long long left = 0;
    long long right = times[times.size()-1] * N;
    long long answer = 0;

    while(left <= right){
        long long mid = (left + right) / 2;
        
        long long total = 0;
        for(int i=0; i<times.size(); i++){
            total += mid / times[i];
        }

        if(total < N){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }

    return left;
}

• 이분탐색으로 푸는 문제.
• 8번 테스트케이스에서 계속 오류가 나서 검색 해 보니 인자로 받은 n을 long long으로 타입캐스팅 해주어야 했다 ㅡㅡ.. 애초에 long long으로 주지
• left를 0으로, right를 가장 큰 값 (가장 느린 심사대 * N명 처리)로 해 주었다.
• mid로 탐색하며, mid분에서 몇명을 처리할 수 있는지 확인한다.
• 총 처리 인원이 N보다 작으면 left를 늘려주고, 크면 right를 줄여준다.