백준 3079 [자바] java 입국 심사

문제 링크: https://www.acmicpc.net/problem/3079

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)

---

▶출력

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

---

▶해설

M의 범위가 10억이고, 계산대가 가질 수 있는 값(Tk) 범위는 10억입니다. int 형을 초과되므로 long을 사용해줍니다.

 

최소한의 시간을 구하는 문제입니다. 시간에 주목할 필요가 있습니다.

 

1. 가장 오래 걸리는 시간 -> 가장 오래 걸리는 계산대 * M

그렇다면 시간의 범위는 1 ~ 가장 오래 걸리는 계산대 * M 정의할 수 있습니다. 

 

 

이분 탐색을 하기위해 계산대 걸리는 시간을 정렬한 후 low = 1 high = 가장 오래 걸리는 계산대 * M 설정합니다.

mid = (low+high)/2

long low = 0;
long high = m * max;

count = mid/각 계산대 걸리는 시간 -> 한 계산대에서 맡을 수 있는 사람의 수가 구해집니다.

sum+=count를 진행해서 처리할 수 있는 사람의 수를 구합니다. 이것이 M을 넘는다면 더 이상 진행하지 않습니다. 

for(long index: arr){
    long count = mid/index;
 
    if(sum>=m){ // 이미sum>=M이라면 바로 탈출시킵니다.
        break; 
    }
    sum+=count;
}

count>=M이라면 mid보다 작은 수에서 만족시킬 수 있습니다. 

-> mid = high-1 

-> 최근의 값과 mid를 비교하여, 더 작은 수를 넣어줍니다.

count <M이라면 mid 보다 큰 수 에서 만족시킬 수 있습니다. 

-> mid = low-1

if(sum>=m){
    high = mid-1;
    result = Math.min(mid,result);
}
else{
    low = mid+1;
}

low <=high 만족한다면 계속 진행시킵니다.

while(low<=high){
    long mid = (low+high)/2;
    long sum = 0;
    for(long index: arr){
        long count = mid/index;
        if(sum>=m){
            break;
        }
        sum+=count;
    }
    if(sum>=m){
        high = mid-1;
        result = Math.min(mid,result);
    }
    else{
        low = mid+1;
    }
}

최종 코드입니다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    static int n;
    static long m, max;
    static int [] arr;
    static long result = Long.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
 
        arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(br.readLine());
            max = Math.max(max,arr[i]);
        }
        Arrays.sort(arr);
 
        solve();
 
        System.out.println(result);
    }
 
    private static void solve(){
        long low = 0;
        long high = m * max;
 
        while(low<=high){
            long mid = (low+high)/2;
            long sum = 0;
            for(long index: arr){
                long count = mid/index;
 
                if(sum>=m){
                    break;
                }
                sum+=count;
            }
            if(sum>=m){
                high = mid-1;
                result = Math.min(mid,result);
            }
            else{
                low = mid+1;
            }
        }
    }
}