[Java] 백준 3079. 입국심사

입국심사

문제

상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 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)

 

출력

첫째 줄에 상근이와 친구들이 심사를 마치는데 걸리는 시간의 최솟값을 출력한다.

 

예제 입력 1

7 10
3
8
3
6
9
2
4

예제 출력 1

8

 

 

풀이

시간을 기준으로 이분탐색을 진행해서 심사에 걸리는 최소 시간을 찾아야 한다.

시간의 최대값은 (가장 오래 걸리는 심사대의 시간 * 사람 수)로 정하고, 이분탐색을 위해 배열을 정렬한 후 시작한다.

 

문제에서 주어진 예시로 살펴보자.

심사대의 수(n) = 7, 사람 수(m) = 10, 각 심사대의 시간 = [2, 3, 3, 4, 6, 8, 9]이다. 따라서 최대로 걸릴 수 있는 심사 시간은 9 * 10 = 90이다.

 

중간 값인 45초로 탐색을 시작한다.

첫 번째 심사대가 한 명을 심사하는데 2초가 걸리면 45초 동안 22명이 심사가 가능하다.

하지만 심사해야 할 사람은 총 10명이니 45초보다 작은 시간 안에 수행이 가능하다는 걸 의미한다.

따라서 0-90 → 0-44로 범위를 줄여서 중간 값을 찾고 다시 탐색을 시작한다.

 

만약 계속 줄어들다가 mid = 4가 됐을 때를 생각해보자.

4초 동안 심사가 가능한 사람의 수 = 2 + 1 + 1 + 1 + 0 + 0 + 0 = 5가 된다.

이런 경우 4초보다 작거나 같은 시간에는 모든 사람의 심사가 불가능하다.

 

코드

package Study;

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

public class BOJ_3079 {
    static int n;
    static long m;
    static int[] arr;
    static long MAX_VALUE;
    static long result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // 입국심사대 수
        m = Long.parseLong(st.nextToken()); // 사람 수

        arr = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, arr[i]);
        }
        MAX_VALUE = m * max; //최대로 걸리는 시간 = 사람 수(m) * 가장 오래 걸리는 심사 시간
        result = MAX_VALUE;
        Arrays.sort(arr); //이분탐색을 위해 정렬

        searchMinTime();
        System.out.println(result);
    }

    // 시간을 기준으로 이분탐색을 한다.
    private static void searchMinTime() {
        long lo = 0;
        long hi = MAX_VALUE;

        while (lo <= hi) {
            long mid = (lo + hi) / 2;

            long totalPerson = 0; // 해당 시간에 각 심사대에서 맡는 사람 수의 합
            for (int i : arr) {
                // 해당 시간에 각 심사대에서 맡을 수 있는 사람 수
                long cntPerson = mid / i;

                // 정렬된 배열이기 때문에 현재 심사대의 심사 시간이 검사 중인 시간보다 크거나
                // 현재까지 사람 수의 합이 총 사람 수보다 크면 바로 반복문을 탈출한다.
                if (totalPerson >= m || i > mid) {
                    break;
                }

                totalPerson += cntPerson;
            }

            // totalPerson 값이 총 사람 수보다 크거나 같다면
            // 더 짧은 시간에 완료될 수 있다는 것을 의미한다.
            // 따라서 hi 값을 mid - 1로 설정한다.
            // 반대로 총 사람 수보다 작다면 해당 시간에 심사가 불가능하다는 것을 의미한다.
            if (totalPerson >= m) {
                hi = mid - 1;
                result = Math.min(result, mid);
            } else {
                lo = mid + 1;
            }
        }
    }
}