오늘은 이진탐색 문제를 하나 풀어보았다.
https://www.acmicpc.net/problem/3079
입국심사를 최소 시간을 돌 수 있는 케이스를 찾아보기 위해서
시간을 이분탐색하며 해당 시간에 모두 심사를 마칠수 있는지 체크하는 방식으로 진행했다.
알고리즘은 맞는거 같은데 틀리길래 확인해보니 나는 최대로 오래걸리는 입국심사위원 * 대상자가 최대 시간이라 생각했는데 이러면 overflow가 나오는거 같다 그리하여 최소입국 심사위원으로 변경하니 해결되었다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
* https://www.acmicpc.net/problem/3079
*/
public class Main {
public static void main(String[] args) throws IOException {
binarySearch();
}
public static void binarySearch() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
long[] gate = new long[N];
long min = Integer.MAX_VALUE;
for (int i=0 ; i < N; i++) {
gate[i] = Integer.parseInt(br.readLine());
min = Math.min(min, gate[i]);
}
long time = binarySearch(0, min * M, gate, M);
System.out.println(time);
}
public static long binarySearch(long start, long end, long[] gate, int count) {
if (start > end) {
return start;
}
long mid = (start + end) / 2; // 중간 시간
long sum = 0; // 통과 누적 수
for (long j : gate) sum += mid / j;
if (sum > count) { // 시간이 널널
return binarySearch(start, mid - 1, gate, count);
} else if (sum < count) { // 시간 부족
return binarySearch(mid + 1, end, gate, count);
} else {
return binarySearch(start, mid - 1, gate, count);
}
}
}
결과
'Coding Test' 카테고리의 다른 글
백준 사격(31264) (0) | 2024.03.09 |
---|---|
백준 두 수의 합(9024) (0) | 2024.03.08 |
백준 개똥벌레 (3020) (0) | 2024.03.04 |
백준 시간관리(1263) (0) | 2024.03.03 |
백준 숌 사이 수열(1469) (0) | 2024.03.02 |