[알고리즘] 백준 3079 - 입국심사

1. 문제

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

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

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

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

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

2. 입력

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

3. 풀이

최소값 -> 매개변수탐색(이분탐색)

1. 문제 바꾸기

원래 문제

• 조건 : 인원이 m명일 때
• 타겟 : 최소 시간 t

뒤집은 문제

• 조건 : 시간이 t일때
• 타겟 : 인원 m명만큼 검사할 수 있는지

2. 이분탐색

1) 시간(t)동안 m만큼의 인원을 심사할 수 있는지 검사
2) t에 대해서 이분탐색 진행
3) 최소 시간 이후로는 m만큼의 인원을 심사할 수 없음
-> m만큼의 인원을 심사할 수 있는 마지막 시간이 정답

4. 코드

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

public class immigration_3079 {

    static int n,m;
    static int[] time;

    public static void solution() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine()," ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        time = new int[n];
        for(int i=0;i<n;i++){
            time[i] = Integer.parseInt(bf.readLine());
        }

        Arrays.sort(time);

        //이분탐색하기(시간을)
        //매개변수탐색

        long left = 0;
        long right = Long.MAX_VALUE;
        long mid; //심사 받는데 주어진 시간

        long answer = Long.MAX_VALUE;

        while(left<=right){
            mid = (left+right)/2;

            //현재 시간(mid)으로 심사 가능하면
            if(determination(mid)){
                answer = mid;
                right = mid-1;
            }
            else{
                left = mid+1;
            }
        }

        System.out.println(answer);
    }

    //시간(mid == t)동안 m만큼의 인원을 심사할 수 있는지
    public static boolean determination(long t){
        long sum = 0;//주어진 시간(mid)동안 심사를 받을 수 있는 사람 수
        for(int i=0;i<n;i++){
            sum += t/time[i];

            if(sum>=m){
                break;
            }
        }

        return sum >= m;

    }
}