[BOJ-3079] 입국심사(JAVA)

 

백준 3079 입국 심사

 

https://www.acmicpc.net/problem/3079

3079번: 입국심사

 

 

문제 설명

 

 - 상근이와 친구들은 오스트레일리아로 여행을 떠났다.

 

 - 상근이와 친구들은 총 M명이고, 한 줄로 서서 입국심사를 기다리고 있다.

 

 - 입국 심사대는 총 N개가 있다.

 

 - 각 입국 심사관이 심사를 하는데 걸리는 시간은 Tk이다.

 

 - 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다.

 

 - 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다.

 

 - 심사를 받기 위해 항상 이동을 해야 하는 것이 아니라, 더 빠른 심사대의 심사가 끝나길 기다린 다음

   그 곳에서 심사를 받아도 된다.

 

 - 상근이와 친구들이 심사를 받는데 걸리는 시간의 최솟값을 구하라.

---

 

입력 값

 

 - 첫째 줄에 N과 M이 주어진다.

   ( 1 <= N <= 100,000 / 1 <= M <= 1,000,000,000 )

 

 - 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. ( 1 <= Tk <= 1,000,000,000 )

 

---

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 상근이와 친구들이 심사를 마치는 최소 시간을 구하는 문제이다.

 

 - 간단하게 생각해보자면, M명의 사람이 있고, 심사대가 N개 있기 때문에 모든 경우의 수는 $M^N$이 된다.

   M의 최댓값은 1억이고, N의 최댓값은 10만이다. 즉 불가능하다.

 

 - 그렇다면 어떻게 해야 할까?

 

 - 이 것의 정답 형태를 살펴보면 힌트를 찾을 수 있다.

 

 - 정답이 되는 최소 시간을 T라고 가정해보자.

 

 - T보다 큰 값인 T+1, T+2, ... 의 시간으로는 당연히 심사를 마칠 수 있다.

   왜냐하면, 마치는 시간이 아니라, 그 시간안에 끝낼 수 있는지를 판단하기 때문이다.

   

 - 반면, T보다 작은 T-1, T-2, T-3, ... 1 은 당연히 심사를 마칠 수 있다.

   왜냐하면, 마치는 최소 시간이 T이기 때문이다.

 

 - 즉, 이 문제는 파라메트릭 서치를 이용할 수 있는 조건을 가지고 있다.

파라메트릭 서치(Parametric Search)

 

 - 심사를 마치는 최소 값은 M=1이고, N=1 이고, Tk=1인 상태이므로 1이다.

 

 - 심사를 마치는 최대 값은  M=1억이고, N=1이고, Tk=1억인 상태이므로 1조이다.

 

 - 심사를 마치는 최대, 최소 사이의 중간 값을 바탕으로 가능한지 판단하면 된다.

 

 - 해당 시간 안에 심사가 가능한지 판단하는 방법은 다음과 같다.

   1. 해당 시간인 TIME를 구한다.

   2. 각 심사대에서 mid 시간 안에 몇 명이 심사를 받을 수 있는지 구한다.

   3. 각 심사대에서 심사 받을 수 있는 인원을 모두 더하여 M보다 크거나 같은지 확인한다.

   4. M보다 작다면, TIME안에 불가능 하다는 것이도, M보다 크거나 같다면 TIME안에 가능하다는 것이다. 

 

 - 이 문제에서 주의할 점은 인원을 측정하는 과정에서 언더플로/오버플로를 조심해야 한다는 것이다.

 

---

 

 

소스 코드

 

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

// https://www.acmicpc.net/problem/3079
// 입국심사
public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N;
        long M;

        StringTokenizer st = new StringTokenizer(bf.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Long.parseLong(st.nextToken());

        long times[] = new long[N];

        for(int i=0;i<N;i++){
            times[i]=Long.parseLong(bf.readLine());
        }

        // last => 끝나는 시간의 최대값.
        long start = 1;
        long last = 1000000000000000000L;
        long result=last;


        while(start <= last){
            // mid로 끝나는 시간 기준으로 각 부분에서 몇 명을 처리할 수 있는가
            long mid = (start+last)/2;

            if(check(M,mid,times)){
                last=mid-1;
                result = Long.min(result,mid);
            }
            else{
                start=mid+1;
            }
        }
        System.out.println(result);
    }

    public static boolean check(long M,long mid, long times[]){
        for(int i=0;i<times.length;i++){
            M-=mid/times[i];
            // 이거 안해주면 언더플로 가능
            if(M<=0){
                return true;
            }
        }
        return false;
    }
}