[백준]3079번 입국심사 - C++

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)

출력

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

---

숫자의 범위가 굉장히 크다. 

심사대는 10만개 까지 있을 수 있으며 심사대 별로 걸리는 시간은 1억이다.

친구는 1억명 까지 있을 수 있다.

이분 탐색을 활용하여 0(s)~ 최댓값(e)으로 시작하여 중앙값 mid의 시간이 있을 때 총 몇 명의 사람을 태울 수 있는지 확인한다.

이때 최대값은 가장 비효율적인 여러 개의 심사대 중 가장 오래 걸리는 시간 * 친구의 수로 설정할 수 있다.

 

mid의 시간에 확인 가능한 사람 sum 은 mid/[심사대별 걸리는 시간]의 합으로 확인할 수 있다.

sum이 M 보다 크다면 시간이 넉넉 하므로 e를 줄여준다. 다만 해당 시간으로 M 명은 태울 수 있으므로 ans값을 mid로 최신화한다.

sum이 M 보다 작다면 시간이 부족하므로 s를 늘려준다.

---

처음에 dp로 풀어야 하나 생각했지만 숫자가 너무 컸다. 당장의 선택이 이득이 되지 않으므로 그리디도 아니라고 생각했다. 그래서 다른 풀이 방법을 생각했는데 이렇다 할 방법이 떠오르지 않아 분류를 봤더니 이분탐색이었다. NM 만 하더라도 10만 * 1억이라 시간 초과가 나서 로그 시간을 사용하여야 했고 로그 시간하면 이분 탐색을 떠올렸어야 했는데 그러지 못했다. 그리고 숫자가 너무 클 것이라고 생각했는데 최댓값 역시 1억 * 1억이 최대이고 이는 나름 큰 수 이기는 하지만 long long으로 충분히 다룰 수 있다. 또한 NlogM의 경우 10^9 승은 2^60 정도와 같아 60 * 10만으로 굉장히 숫자가 작아진다. 대충 너무 오래 걸리지 않나 하고 더 깊이 생각하지 않았던 게 패착이었다. 그래도 내가 생각해내지 못한 것과 어떻게 생각해 내야 할지를 고민한 것은 얻어간 것 같다.