[Java] 프로그래머스 43238.입국심사 (Lv.3)

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

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

 

이분탐색의 기본적인 응용문제입니다.

가능한 정답의 최소시간 = 1과 확실하게 가능한 정답중의 하나 = ((대기자의 수 / 심사관의 수) + 1 ) * 가장 느린 심사속도 두개를 시작점으로 해서 이분탐색을 돌리면 됩니다.

 

이분 탐색 문제는 언제나 탐색을 멈추는 조건을 정하는게 어려운데, 문제가 보통 정답의 최댓값이나 최솟값을 요구합니다. 우리는 문제에 따라 확실하게 가능한 정답과 확실하게 정답이 아닌 것+1을 줄여가다가 둘이 겹치는 곳에서 문제가 요구하는 답을 찾을 수 있습니다.

 

public class q43238_Programmers_입국심사 {

	public static void main(String[] args) {

		int n = 6;
		int[] times = { 7, 10 };

		System.out.println(solution(n, times));
	}

	private static long solution(int n, int[] times) {
		long answer = 0;

		long max = 0;

		for (int t = 0; t < times.length; t++) {
			max = Math.max(max, times[t]);
		}

		long left = 1;
		long right = ((n / times.length) + 1) * max;

		while (left < right) {
			long center = (left + right) / 2;
			long count = 0;

			for (int t = 0; t < times.length; t++) {
				count += (center / times[t]);
			}
			
			if(count >= n) {
				right = center;
			}else {
				left = center + 1;
			}

		}

		answer = right;
		return answer;
	}
}