심사대의 상태나 사람의 명수가 어떻든 '결국에 최소로 진행될 수 있는 시간' Tans 가 있다고 하겠습니다.
그러면 이 T가 존재할 수 있는 범위에 대해서 먼저 생각해보면
제일 시간이 오래걸리는 심사대에서 걸리는 시간 Tmax 에 사람 수 N을 곱한 값이 될 것입니다. N명이 모두 Tmax에서만 심사를 받는 경우에요.
최소는 대충 1이라고 잡아도 되겠습니다. Tk의 범위는 1이상이니까요
그러면 이제 어떤 시간 Tk 를 정해놓겠습니다.
그리고 Tk초 안에 모든 사람이 심사대에 통과할 수 있는지 알아봅니다.
모든 사람이 Tk초 안에 심사대를 통과할 수 있으면 Tk가 Tans가 될 수도있고, 아니면 더 적은시간에도 가능할 수도 있겠죠.
반대로 모든 사람이 Tk초 안에 심사대를 통과할 수 없으면 Tk는 정답이 될 수 없습니다. 더 많은 시간이 필요하죠.
그러면 이제 모든 사람이 Tk초 안에 심사대를 통과할 수 있는지 없는지를 알아봐야합니다.
모든 사람이 Tk초 안에 통과할 수 있으려면 '각 심사대에서 Tk초 동안 통과시킬 수 있는 사람 수'를 각각 구해서 더해보고 그게 N명 이상이면 가능하다는 뜻입니다.
그래서 count += mid//time 을 하는 것입니다.
Tk로 Tans를 찾아내는 과정을 이분탐색으로 진행할 수 있습니다
hsw0194 2년 전 2
파이썬 기준으로
for time in times
count +=mid//time
을 하는 이유에 대해서 궁금합니다. 정확히 말하면 잘 와닿지가 않습니다.
예를 들어서 예시 데이터에서 n=6,[7,10]이고 시간이 20초일때 빈 심사대인 (10초 심사대)로 가지 않고 1초를 기다린 후에
첫번째 심사대(7초 심사대)로 가는 과정이 있는데, count +=mid//time 처럼 단순한 식으로 저런 과정을 포함할수 있나에 대해서
의문입니다.
정리하자면 빈 심사대가 있어도 심사를 받지 않고 1초를 기다리는 등의 복잡한 과정이 있는데 mid//time같은 단순한 식으로 바뀌는것이 궁금합니다.
정말 많은 해설 풀이글을 찾아봤지만 기다리는 과정까지 포함한 설명이 없더라구요. 도움 부탁드립니다.