문제설명

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

접근

  • 문제 분류 자체가 이분 탐색으로 되어 있었기에 이분 탐색으로 접근했다…ㅎ

내가 생각한 풀이

  • mid를 times의 원소로 나눈 후 그 합을 구한다. 이 합이 n보다 작으면 left를 증가시켜주고 그렇지 않으면 right를 감소시키고 answer를 계속 업데이트 시켜준다. (최소값을 구해야 하기 때문에 조건을 만족하는 수 중에서도 가장 작은 값을 찾아야 한다.)

함정

  • 이 문제의 worst case는 1,000,000,000,000,000,000 이다. long long으로 이를 충분히 커버할 수 있다고 생각했으나 이상하게 8번 테스트 케이스를 통과하지 못했다. 혹시나 하는 마음으로 unsigned long long으로 바꿔줬더니 정답으로 인정이 되었다.
    • 나 같은 경우 n = 1000000000 times는 [1000000000, 1000000000] return은 500000000000000000을 테스트케이스로 추가해서 오류를 잡았다.
    • 구글링을 통해 long long의 범위가 -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 인 것을 확인하고 문제를 풀었는데 조금 이상했다… 왜 그런지 이유를 찾아봐야겠다.

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long solution(int n, vector<int> times) {
  long long answer = 0;
  sort(times.begin(), times.end());
  unsigned long long left = 0, right = n * times[times.size() - 1];
  while(left <= right)
  {
      unsigned long long mid = (left + right) / 2, sum = 0;
      for(int i = 0 ; i<times.size() ; i++)
      {
          sum += mid / times[i];
      }
      if(sum < n)
      {
          left = mid + 1;
      }
      else
      {
          right = mid - 1;
          answer = mid;
      }
  }
  return answer;
}