[Programmers] 입국심사 - 이분탐색

import java.util.Arrays;

// 입국심사 - 이분탐색
public class Immigration {
	public long solution(int n, int[] times) {
		Arrays.sort(times);
		long left = 0, right = (long) times[times.length - 1] * (long) n, mid, cnt, answer = Long.MAX_VALUE; // Overflow 주의
		// right는 입국심사가 가장 오래걸리는 시간으로 초기화

		while (left <= right) {
			cnt = 0;
			mid = (left + right) / 2;
			for (long t : times) {
				cnt += mid / t;
			}
			if (cnt < n) { // n명을 다 처리하지 못했을 경우
				left = mid + 1;
			} else { // n명을 다 처리했을 경우 (최소값을 구해야함)
				answer = Math.min(answer, mid);
				right = mid - 1;
			}
		}
		return answer;
	}
}