프로그래머스 : 입국심사

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

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

 

​

각 심사관이 심사하는 시간이 a라면, b라는 시간 안에 처리할 수 있는 사람의 수는 b / a 입니다.

모든 심사관의 처리할 수 있는 사람의 수가 n보다 크거나 같다면, 이분 탐색으로 시간 범위를 줄여나가면 됩니다.

left = 1, right = 처리하는데 가장 오래 걸리는 심사관의 시간 * n 으로 초기화한 뒤에 진행하였습니다.

#include <string>
#include <vector>
using namespace std;

int extractMaxTime(vector<int>& times) {
    int max = -1;
    for(int time : times) {
        if(max < time) max = time;
    }
    return max;
}

long long solution(int n, vector<int> times) {
    long long l = 1, r = (long long)extractMaxTime(times) * n;
    while(l <= r) {
        long long sum = 0;
        long long mid = (l + r) / 2; // 처리하는데 걸리는 시간
        for(int time : times) {
            sum += mid / time; // 각 심사관이 mid시간 안에 처리할 수 있는 사람 수
        }
        if(n <= sum) { // 처리 가능한 시간인 경우
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return l;
}