입국심사 [백준 3079][Java][이분탐색]

[광고 누르면 오늘의 행운 상승!!]

이분탐색 문제

1. long으로 지정해 주어야 오버플로우가 발생하지 않는다.

2. mid 를 left + right가 아니라 left + (right - left)/2 로 지정하였다.
left+right는 오버플로우가 발생할 가능성이 있다.

3. isImpossible을 이용하여 최소시간을 구해나간다.

import java.io.*;
import java.util.*;

public class Main {

	static long n, m;
	static long[] time;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Long.parseLong(st.nextToken());
		m = Long.parseLong(st.nextToken());

		time = new long[(int) n];
		long max = 0;
		for (int i = 0; i < n; i++) {
			time[i] = Long.parseLong(br.readLine());
			max = Math.max(max, time[i]);
		}

		binarySearch(max * m);

	}

	private static void binarySearch(long r) {
		long left = 1;
		long right = r;
		long result = right;
		long mid = 0;

		while (left <= right) {
			mid = left + (right - left) / 2;

			if (isPossible(mid)) {
				result = Math.min(result, mid);
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}

		System.out.println(result);
	}

	private static boolean isPossible(long t) {
		long temp = 0;
		for (int i = 0; i < n; i++) {
			temp += t / time[i];
		}
		return temp >= m;
	}
}