문제 설명
📃 문제 링크
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
- 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
- 심사관은 1명 이상 100,000명 이하입니다.
입출력 예
| n | times | return |
|---|---|---|
| 6 | [7, 10] | 28 |
입출력 예 설명
가장 첫 두 사람은 바로 심사를 받으러 갑니다.
7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.
10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.
14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.
20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.
문제 풀이
어떤 것을 기준으로 놓고 이분 탐색을 해야 하는지 감이 잡히지 않아서 어려웠던 문제였다.
또 주어진 테스트 케이스의 설명 중,
20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.
이 부분을 어떻게 처리해야 할 지 고민이 많이 되었는데, 모든 심사대에서 연속적으로 심사받게 하면서 가장 최적의 시간을 찾아나가면(?) 해결이 되는 것 같다. 즉, 6명이기 때문에 각 심사대에 3명씩 (7*3),(10*3)으로 총 시간 30분으로도 심사받을 수 있지만, (7*4), (10*2) 로 7분 심사대에서 4명을 심사하는 28분이 최적의 시간이다. 가장 최적의 시간을 찾기 위해서는 시간이 적게 걸리는 심사대에서 최대한 많은 심사를 해야 한다.
전체 로직은 주어진 심사대와 주어진 인원 수에서 가장 오래 걸리는 최악의 심사 시간을 max로 두고, 시간을 이진 탐색 하면서 현재 탐색하는 시간(mid)동안 심사가 가능한지 판단한다. 더 많은 인원을 심사할 수 있다면 현재 탐색한 시간보다 아래쪽에서 다시 찾고, 심사해야 하는 인원수보다 현재 심사 가능한 인원수가 더 작다면 위쪽에서 다시 찾는다.
이 때, mid 즉, 현재 탐색하고 있는 시간을 심사대 [7,10] 각 요소의 수로 나누고 나머지는 버리기 때문에 결국 7심사대로 나눈 몫이 더 큰 수가 최적의 시간으로 나오게 될 것이다. 문제의 답처럼 7심사대에서 4명, 10심사대에서 2명을 심사하는 경우가 아니라, 10심사대에서 4명을 심사한다고 가정해보자. 그렇다면 현재 탐색하고 있는 수는 적어도 40 이상일 것이고, 7심사대에서는 적어도 5명을 심사할 수 있기 때문에 4+5 = 9가 되어 9명을 심사할 수 있게 된다. 즉, 같은 수를 7과 10으로 나누는 것이기 때문에 나누는 수가 작을 수록 몫이 클 수 밖에 없다. 이 때에는 주어진 인원보다 더 많은 인원을 심사할 수 있는 경우이기 때문에 시간을 더 아래쪽에서 찾아 줄여 나가야 한다.
사실 아직도 완벽하게 이해가 안 됐다. 넘 어려워
소스 코드
.png)
