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

프로그래머스

 

• 이분탐색 문제
• 데이터 타입에 주의하자

 

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

using namespace std;

/*
이분 탐색
최소 시간을 1명을 1분으로 끝낸다고 가정하면 1
최대 시간은 가장 오래 걸리는 심사원에게 모든 인원이 심사를 받으러 갔을 때
위 둘을 각각 left, right로 하여 이분탐색 직행
mid를 각 심사위원이 심사하는데 걸리는 시간으로 나눈 값을 더하면 mid분일 때 심사할 수 있는 인원이 나옴
mid분에서 처리할 수 있는 인원이 n보다 크면 right를 mid - 1로 하고 작으면 left를 mid + 1로 해서 계속 탐색
left == right가 되면 탐색을 중단
*/

long long solution(int n, vector<int> times) {
    long long answer = 0;
    
    // times 배열 정렬
    sort(times.begin(), times.end());
    
    // 최소 시간
    long long left = 1;
    // 최대 시간, 데이터 타입에 주의
    long long right = n * (long long)times.back();
    
    while(left <= right) {
        long long mid = (left + right) / 2;
        
        // mid분에서 심사를 끝낼 수 있는 인원 수
        long long cnt = 0;
        
        for(int i = 0; i < times.size(); i++)
            cnt += mid / (long long)times[i];
        
        // n보다 많거나 같은 수의 인원의 심사를 끝낼 수 있다면
        if(cnt >= n) {
            right = mid - 1;
            answer = mid;
        }
        // n 보다 적은 수의 인원의 심사를 끝낼 수 있다면
        else {
            left = mid + 1;
        }
    }
    
    
    return answer;
}