Programers 입국 심사

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

프로그래머스

프로그래머스 입국심사 문제입니다.

 

아이디어

이분탐색을 이용하여 풀이했습니다. 이분탐색문제는 이분탐색을 위한 최솟값과 최댓값을 판단하는 부분이 풀이의 방향에 중요한 역활을 한다고 느껴십니다.

 

#include <string>
#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 start = 1;
	//범위의 최댓값
	long long end = (long long)times[times.size() - 1] * n;
	long long mid = 0;
	while (start <= end) {
		mid = (start + end) / 2;
		long long temp = 0;

		//해당 시간안에 심사를 받을 수 있는 사람의 최솟값을 구함
		for (auto iter : times)
			temp += (mid / iter);

		//사람이 부족하다면 최솟값을 늘려야함
		if (temp < n) {
			start = mid + 1;
			continue;
		}
		//현재까지의 최솟값을 저장해 둠
		if (mid <= end)
			answer = mid;

		//사람이 남는다면 최댓값을 줄여야함
		end = mid - 1;

	}
	return answer;
}