문제
N개의 심사대가 각각 다른 시간이 걸린다. M명이 모두 심사를 받는 최소 시간을 구하라.
입력
첫째 줄에 N, M, 이후 N개의 심사 시간이 주어진다.
출력
모든 사람이 심사를 받는 최소 시간을 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 6 7 10 | 28 |
풀이
매개 변수 탐색으로 "시간 T 내에 M명 이상 심사할 수 있는가?"를 판별한다.
- 탐색 범위: 1부터 10^18까지 이분 탐색한다
- 중간값 mid 시간 동안 각 심사대에서
mid / 심사시간명을 처리할 수 있다 - 전체 처리 가능 인원이 M 이상이면 시간을 줄이고, 미만이면 늘린다
- 오버플로우 방지를 위해 합산 중 M 이상이 되면 조기 종료한다
핵심 아이디어: "최소 시간" 문제를 "T 시간이 충분한가?"라는 결정 문제로 변환하여 이분 탐색한다.
코드
package day449;
import java.io.*;
import java.util.*;
public class Day410BOJ3079입국심사 {
static int N, M;
static int[] arr;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
long l = 1;
long r = 1_000_000_000_000_000_000L;
while (l <= r) {
long mid = (l + r) / 2;
long temp = 0;
for (int num : arr) {
temp += (mid / num);
if (temp >= M)
break;
}
if (temp >= M) {
r = mid - 1;
} else {
l = mid + 1;
}
}
System.out.println(l);
br.close();
}
}복잡도
- 시간: O(N log(max * M)) - 이분 탐색 × 판별 O(N)
- 공간: O(N)