hsw0194   2년 전

파이썬 기준으로

for time in times
count +=mid//time

을 하는 이유에 대해서 궁금합니다. 정확히 말하면 잘 와닿지가 않습니다.

예를 들어서 예시 데이터에서 n=6,[7,10]이고 시간이 20초일때 빈 심사대인 (10초 심사대)로 가지 않고 1초를 기다린 후에

첫번째 심사대(7초 심사대)로 가는 과정이 있는데, count +=mid//time 처럼 단순한 식으로 저런 과정을 포함할수 있나에 대해서

의문입니다.

정리하자면 빈 심사대가 있어도 심사를 받지 않고 1초를 기다리는 등의 복잡한 과정이 있는데 mid//time같은 단순한 식으로 바뀌는것이 궁금합니다.

정말 많은 해설 풀이글을 찾아봤지만 기다리는 과정까지 포함한 설명이 없더라구요. 도움 부탁드립니다.

pmn0001   2년 전

심사대의 상태나 사람의 명수가 어떻든 '결국에 최소로 진행될 수 있는 시간' 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년 전

저 부분을 제외한 나머지 부분은 다 이해가 잘 갑니다.

pmn0001   2년 전

심사대가 2대가 있고 1번 심사대는 10초에 한명, 2번 심사대는 3초에 한명을 통과시킬 수 있다고하면

Tk가 20초 일때 1번 심사대는 최대 2명을 통과시킬 수 있고, 2번 심사대는 최대 6명을 통과시킬 수 있습니다.

따라서 20초 동안 최대 8명을 통과시킬 수 있는 공항입니다.

도움이 됐을까요

hsw0194   2년 전

네 나머지 부분은 다 이해가 가는데

''각 심사대에서 Tk초 동안 통과시킬 수 있는 사람 수'를 각각 구해서 더해보고 그게 N명 이상이면'을 구하는 부분에서

count+=가 mid//time처럼 간단한 식으로 나오는 방식이 잘 이해가 안갑니다..

각 심사대가 통과시킬수 있는 사람이 매 초마다 사람들이 심사대의 상태를 보고 선택을 할텐데(비어있는 곳으로 갈지,n초 기다려서 빠른 심사대로 갈지)

심사대의 상태를 보고 선택하는것은 꽤 복잡한데 심사대에서 Tk초 동안 통과시킬수 잇는 사람의 수를 구하는 식이 너무 간단해보여서요. 예를들어서 10초인 심사대는 20초일때부터 쭉 쉬는데 이런것도 다 count+=mid/10에 고려가 되는가요? 직관적으로 와닿지가 않네요 ㅠㅠ

pmn0001   2년 전

심사대의 상태를 보고 사람이 심사대를 선택한다고 생각하셔서 이해가 안가시는 것 같습니다.

심사대의 기준으로 생각해야합니다.

우리 공항은 10초, 3초 심사대가 있는데, 20초동안은 최대 8명을 통과시킬 수 있다. 이런식으로요

hsw0194   2년 전

감사합니다 조금더 생각해보겠습니다

hsw0194   2년 전

문제에 주어진 조건들이 혹시

N초안에 가장 많은 사람들을 심사할수 있게끔 보장해주는건가요?? 

그 보장이 있기 때문에 count+=mid//times가 n초동안 심사가 가능한 사람의 합이 되는건가 라는 생각을 했습니다.


pmn0001   2년 전

n초가 현재 확인하고자하는 시간이라면

n초동안 최대로 심사 가능한 사람의 합을 구하는 과정이 count+= mid//times 입니다.

huozuyinshua   2년 전

상태를 보고 선택하는 게 아니라 무한한 사람이 심사대 앞에 있고 미션은 n명이 통과하는 겁니다. 사람들은 줄을 바꾸지 않는다고 생각하는 게 맞는 것 같아요, n 초안에 사람들은 최대한 통과하려 시도합니다. 10초인 심사대도 쉬지 않고 통과시키지만 3초 심사대에서 사람이 쏟아지면서 통과한 사람이 n명이 되여서 시뮬레이션이 끝나게 됩니다.

댓글을 작성하려면 로그인해야 합니다.