[백준] 3079 : 입국심사 - Java

• 백준 문제 URL

---

문제 요약

입국 심사대 n개가 있고, 각 심사대마다 1인당 소요 시간이 다르다.
입국 대기열에 m명이 줄을 서있을 때, 모든 사람이 심사를 받는 데 필요한 최소 시간을 구한다.

즉,

• 심사대 i는 시간 times[i]마다 1명 처리
• 총 m명을 모두 처리하는 최소 소요 시간을 찾는다.

---

핵심 아이디어

시간을 이진 탐색한다!

일반적인 이진 탐색과 다른 점은 탐색 범위가 매우 큼:

• 최소 시간: 1
• 최대 시간: m * max(times) (가장 느린 심사대로 모두 처리)

중간값 mid초 동안:

• 각 심사대가 처리할 수 있는 인원 = mid / times[i]
• 총 처리 인원 ≥ m → 더 짧은 시간 가능 (end = mid - 1)
• 총 처리 인원 < m → 더 긴 시간 필요 (start = mid + 1)

---

알고리즘 핵심 로직

1. 심사 시간 배열 정렬 (효율적 탐색)
2. start = 1, end = m * max(times)
3. while start <= end:
   mid = (start + end) / 2
   
   totalPeople = 0
   for 각 심사대:
       totalPeople += mid / times[i]
       if totalPeople >= m: break
   
   if totalPeople >= m:
       answer = mid
       end = mid - 1
   else:
       start = mid + 1

핵심: long 타입 필수 (범위가 10^18 수준)

---

전체 코드 (제출용)

package A7이분탐색.BaekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class G3079입국심사 {
    public static void main(String[] args) 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()); // 입국자 수

        int[] times = new int[n];
        for (int i = 0; i < n; i++) {
            times[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(times);

        long start = 1;
        long end = (long) m * times[times.length - 1];

        long min = end;
        while (start <= end) {
            long mid = (start + end) / 2;
            long totalPeople = 0;

            for (int time : times) {
                totalPeople += mid / time;
                if (totalPeople >= m) break;
            }

            if (totalPeople >= m) {
                min = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        System.out.println(min);
    }
}

---

예제 시뮬레이션

입력:

n = 3, m = 6
times = [7, 10, 15]

정렬 후: [7, 10, 15]

이진 탐색 과정:

mid=30: 30/7=4 + 30/10=3 = 7 ≥ 6 → answer=30
mid=15: 15/7=2 + 15/10=1 = 3 < 6 → start=16
mid=22: 22/7=3 + 22/10=2 = 5 < 6 → start=23
mid=25: 25/7=3 + 25/10=2 = 5 < 6 → start=26
...
최소 시간 = 28초

---

핵심 포인트 정리

• 매우 큰 범위 → long 타입 + 적절한 상한 설정 필수
• 시간을 직접 이진 탐색하는 고난도 패턴
• early break 최적화 (totalPeople >= m 시 루프 종료)
• 시간 복잡도: (O(n \log (m \cdot t)))