가능한 정답의 최소시간 = 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;
}
}
import sys
N,M = map(int, sys.stdin.readline().split(' '))
staffs = list(map(int, sys.stdin.readline().split(' ')))
left = 0
right = min(staffs) * M
while(left+1 < right):
center = (left + right)//2
balloon = 0
for n in range(N):
balloon += center//staffs[n]
if(balloon >= M):
right = center
else :
left = center
print(right)
상당히 유익한 글이고 이분 탐색 문제 풀이에서 발생하는 오답을 잡아주기 때문에 저와 비슷한 어려움을 겪으시는 분들은 꼭 읽어보시길 추천드립니다.
구현은 쉽지만 오류 찾기가 어려운 이분 탐색 문제였습니다. 감사합니다!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static StringTokenizer st;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
long N = Integer.parseInt(st.nextToken());
long M = Integer.parseInt(st.nextToken());
long[] staffs = new long[(int) N];
st = new StringTokenizer(br.readLine());
long min = Integer.MAX_VALUE;
for (int n = 0; n < N; n++) {
staffs[n] = Integer.parseInt(st.nextToken());
min = Math.min(min, staffs[n]);
}
long left = 0;
long right = min * M;
while(left+1 < right) {
long center = (left + right)/2;
long balloon = 0;
for (int n = 0; n < N; n++) {
balloon += (center / staffs[n]);
}
if(balloon >= M) {
right = center;
}else {
left = center;
}
}
System.out.println(right);
}
}