백준 3079번: 입국심사

백준 3079번: 입국심사

 

 

- 이분탐색 알고리즘을 활용해야하는 문제입니다.

- 이분탐색의 경계값은 left = 최단 시간 심사대, right = 최장 시간 심사대 * 인원수 입니다.

- total 은 mid시간 동안 검사할 수 있는 총 사람의 수 입니다. total 은 mid시간 // 각 심사대의 소요 시간 의 총합을 구하면 됩니다. mid시간동안 M보다 더 많은 인원을 심사하는 것은 답이 될 수 있지만 M보다 적은 인원을 심사하는 것은 안되므로 total >= M 인 경우와 아닌 경우로 나누어 생각했습니다.

- 파이썬 같은 경우에는 sys를 꼭 import하여 풀어야합니다. sys.stdin.readline()를 활용하여 입력값을 받아야지 시간초과에 안 걸립니다. N이 작을 때에는 문제가 없지만 100,000만큼의 데이터를 받을 때에는 둘의 속도가 상당히 차이가 납니다. 저 역시 처음에 int(input()) 을 이용하여 입력값을 받았는데 계속 시간초과에 걸려 통과하지 못했습니다.

- sys.stdin.readline() 과 input() 의 속도 차이에 관한 자세한 내용을 다룬 정보가 있어서 링크합니다 (www.acmicpc.net/blog/view/56).