알고리즘
[Java] 백준 3079번 입국심사
J3SUNG
2023. 8. 2. 04:25
728x90
이분 탐색 문제입니다.
M명의 친구들이 전부 심사대를 통과하는데 걸리는 시간을 구해야합니다.
심사대는 전부 시간이 다릅니다.
1. 시간을 구합니다.
2. 해당 시간으로 통과할 수 있는 사람들 수를 구합니다.
3-1. 사람들 수가 M보다 많거나 같다면 더 작은 경우가 있는지 확인합니다. => 1
3-2. 사람들 수가 M보다 적다면 불가능 한 경우로 가능한 경우가 있는지 확인합니다. => 1
위의 과정을 반복해서 최적의 결과값을 찾아냅니다.
해당 과정에서 시간을 구하는 과정은 이분탐색을 사용했습니다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
long n = Long.parseLong(st.nextToken());
long m = Long.parseLong(st.nextToken());
long[] arr = new long[(int) n];
long result = 1_000_000_000L * 1_000_000_000L;
for (int i = 0; i < n; ++i) {
arr[i] = Integer.parseInt(br.readLine());
}
long left = 1;
long right = 1_000_000_000L * 1_000_000_000L;
while (left <= right) {
long mid = (left + right) / 2;
if (check(m, mid, arr)) {
right = mid - 1;
result = Math.min(result, mid);
} else {
left = mid + 1;
}
}
bw.write(result + "\n");
bw.close();
}
public static boolean check(long m, long mid, long arr[]) {
for (int i = 0; i < arr.length; ++i) {
m -= mid / arr[i];
if (m <= 0) {
return true;
}
}
return false;
}
}