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

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

코딩테스트 연습 - 입국심사 | 프로그래머스

 

이분탐색으로 분류되어 있는 문제다. 핵심은 이분탐색을 하는데, 입국 심사관이 검사할 수 있는 사람들 수를 맞추면서 가장 최소가 되는 시간을 구하면되는 것이다. 가장 최악의 시간이 되는시간은 가장 오래걸리는 심사관 * 입국인원수이다. 최소의 시간 + 최대의 시간의 중간점을 구해서 이 중간시간으로 몇명을 심사할 수 있는지 나눗셈을 통해 파악한다. 인원수가 n보다 작으면 최소시간을 중간시간 + 1을 해준다. n보다 크거나 같으면 최대시간을 중간시간 -1을 해주되 최소의 시간을 구해야 하므로 중간시간이 전에 구했던 최소시간보다 작으면 지금의 중간시간을 최소시간으로 한다.

 

 

 

#include<vector>
#include<algorithm>

using namespace std;

long long solution(int n, vector<int> times){
	long long answer = 0;

	sort(times.begin(), times.end());
	long long left = 0;
	long long right = (long long)times[times.size() - 1] * (long long)n;
	answer = right;
	while(left <= right){
		long long mid = (left + right) / 2;
		long long cnt = 0;
		for(int i = 0; i < times.size(); i++){
			cnt += (mid / times[i]);
		}
		if(cnt < n){
			left = mid + 1;
		}
		else{
			if(answer > mid) answer = mid;
			right = mid - 1;
		}
	}

	return answer;
}