백준 3079번: 입국심사 (JAVA)

문제

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

출력

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

 

---

 

풀이

 

한 명을 t초에 처리하는 심사대에서 T만큼의 시간 동안 처리하는 인원 수는 T/t 명이 될 것이다. 따라서, T초 동안 모든 입국심사대에서는 총 sigma(T/T_k)명을 처리할 수 있다.

주어진 값을 잘 살펴보면, 심사대(=N)가 1개이고 친구(=M)가 10^9명이고, 한 개의 심사대에서 한 명을 처리하는데 10^9초가 필요하다고 하면 걸리는 시간은 10^18초이다. 반대로, 가장 빨리 끝나는 시간은 1초다. N이 최대 10^5인데, 1부터 10^18까지 초 하나하나마다 탐색하면 당연히 시간 초과가 뜰 수밖에 없다. 따라서 이진 탐색을 해야한다.

10^18까지 가므로 이진 탐색을 할 때 long에 저장을 한다. 또한, 앞서 언급한 sigma(T/T_k)값 같은 경우,

20000 1

1

1

...

1

과 같은 경우를 생각해보면, 5*10^17을 20000번 더하다보니 long이라고 한들 overflow가 난다. 따라서, sigma(T/T_k)의 경우 k=0부터 N-1까지 합하다가 M보다 크거나 같은 경우 바로 break할 필요가 있다. python이였으면 아무 생각없이 했을텐데....!

 

 

배울 점

 

이진 탐색의 endcase 처리에 대해서 조금 와닿는 바가 있다.

숫자의 overflow 문제를 몇 번 겪고나선 문제를 접할 때부터 정수 범위를 생각하곤 하는데, 문제 중간 과정에서도 정수 범위를 꾸준히 생각해야 한다는 점을 느꼈다.

백준이 https://www.acmicpc.net/board/view/48507 와 같은 분들 덕분(?)에 테스트케이스가 빡세져서 사고력 개선에 도움이 된다. 머리 깨지면서 어렵게 배워야 오래 남는다. 

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
	
    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());
        int M = Integer.parseInt(st.nextToken());

        int[] customs = new int[N];
        for (int i = 0; i < N; i++) {
            customs[i] = Integer.parseInt(br.readLine());
        }

        long start = 1;
        long end = 1_000_000_000_000_000_000L;

        while (start <= end) {
            long mid = (start + end) / 2;
            long temp = 0;
            for (int num: customs) {
                temp += (mid / num);
                if (temp >= M) break;
            }
            if (temp >= M) {
                end = mid - 1;
            }
            else {
                start = mid + 1;
            }
        }
        System.out.println(start);
    }

}