[백준/JAVA] BOJ 3079 - 입국심사

이분탐색을 이용해 최적의 해를 찾아 봅시다

👀 문제

3079번: 입국심사 ✨ 골드 5

상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다.

가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다. 하지만 항상 이동을 해야 하는 것은 아니다. 더 빠른 심사대의 심사가 끝나길 기다린 다음에 그 곳으로 가서 심사를 받아도 된다.

상근이와 친구들은 모두 컴퓨터 공학과 학생이기 때문에, 어떻게 심사를 받으면 모든 사람이 심사를 받는데 걸리는 시간이 최소가 될지 궁금해졌다.

예를 들어, 두 심사대가 있고, 심사를 하는데 걸리는 시간이 각각 7초와 10초라고 하자. 줄에 서 있는 사람이 6명이라면, 가장 첫 두 사람은 즉시 심사를 받으러 가게 된다. 7초가 되었을 때, 첫 번째 심사대는 비어있게 되고, 세 번째 사람이 그곳으로 이동해서 심사를 받으면 된다. 10초가 되는 순간, 네 번째 사람이 이곳으로 이동해서 심사를 받으면 되고, 14초가 되었을 때는 다섯 번째 사람이 첫 번째 심사대로 이동해서 심사를 받으면 된다. 20초가 되었을 때, 두 번째 심사대가 비어있게 된다. 하지만, 여섯 번째 사람이 그 곳으로 이동하지 않고, 1초를 더 기다린 다음에 첫 번째 심사대로 이동해서 심사를 받으면, 모든 사람이 심사를 받는데 걸리는 시간이 28초가 된다. 만약, 마지막 사람이 1초를 더 기다리지않고, 첫 번째 심사대로 이동하지 않았다면, 모든 사람이 심사를 받는데 걸리는 시간이 30초가 되게 된다.

상근이와 친구들이 심사를 받는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000)
다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109)

예제 입력

2 6
7
10

예제 출력

28

🔑 키포인트

이분 탐색 매개변수 탐색

✍️ 코드

🔥 범위에 주의해서 풀어야 함

1️⃣ 이분탐색을 이용해 최적의 시간을 찾는 것이기 때문에 start = 0, end = max(심사시간) * m(사람 수)

2️⃣ 이분탐색 진행: mid 시간 동안 심사할 수 있는 사람 수가 m 이상이라면 시간을 줄여야 하니 end = mid - 1, 미만이라면 시간 늘려야 하니 start = mid + 1

📍 이때, 계산에서 가능한 사람 수가 m보다 커졌다면 break, 아니면 오버플로우 발생 (이유는 백준 질문 게시판 답변을 참고하였습니다)

• 10억 시간이 소요되는 창구 하나와 1의 시간이 소요되는 창구가 최대(9999만개)로 존재할 경우
• 10억명의 사람이 존재한다면, 이분탐색은 다음과 같다
• 최대 소요시간(end) = 10억 * 10억
• 첫 번째 루프에서 mid는 50억이라는 값이 나오게 되고, 수용 가능한 인원을 더하는 과정에서 1의 시간이 소요되는 창구 때문에 able += 10억 * 5억 / 1 이라는 연산이 9999만번 발생
• 이 경우, 값이 대략 2^75로, long 타입의 범위인 2^64를 넘어 오버플로우가 발생

3️⃣ 가능한 인원이 m 이상이라면 answer 갱신

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

public class BOJ3079_입국심사 {
    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()); // 심사대 개수
        long m = Long.parseLong(st.nextToken()); // 사람 수
        int[] arr = new int[n];

        long start = 0;
        long end = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            end = Math.max(end, arr[i]);
        }
        end *= m; // 제일 최대로 걸리는 시간 (최악의 경우)

        long answer = end;

        // 이분탐색으로 가능한 최소 시간 찾기
        while (start <= end) {
            long mid = (start + end) / 2;
            long able = 0;
            for (int time : arr) {
                able += mid / time;
                // 오버플로우 발생할 수 있으므로 m보다 크면 break
                if (able > m) {
                    break;
                }
            }
            if (able >= m) {
                end = mid - 1; // 시간 줄여요
                answer = mid;
            } else {
                start = mid + 1; // 시간 늘려요
            }
        }
        System.out.println(answer);
    }
}