[C++] 입국심사

문제 디버깅 노트 문제를 보고 "이게 어떻게 이진탐색 문제이지?"라는 생각이 들었다. 처음에 풀었던 방식은 시간을 기준으로 각 심사관의 심사시간의 배수만큼의 시간이 흐르면 n--를 해주는 방식으로 풀었다.(마지막 사람이 시간은 오래걸리더라도 현재는 빈 심사관에게 갈지, 조금 기다렸다가 시간이 조금 걸리는 심사관에게 갈지에 대한 로직은 별도 구현) 하지만 예상했던바와 같이 시간초과가 걸렸고 결국 이진탐색으로 풀어야 한다는 것을 깨달았다. 그렇다면 최소 시간을 찾기 위해 어디서부터 어디까지의 범위에 대한 이진 탐색을 수행해야 할까? 최소 범위와 최대 범위를 구해야한다. 문제에서 최소 시간은 0, 최대 시간은 '검사시간이 가장 오래걸리는 심사관' * n(10*6)일 것이다. 그 범위에서 중간값을 계산하고, 그 중간값이 사람들을 얼마나 수용할 수 있는지 본다. 중간값 30이면 7명(30/7+30/10)을 수용할 수 있다. 그 값을 기준으로 이진 탐색을 반복한다. 7명은 n인 6을 초과하니,...

원문링크 : [C++] 입국심사