swj0324   3년 전

이 문제의 해결 방식은 흔히 알려진 회의실 배정 문제처럼 

가장 먼저 도착(배달)되는 택배(회의실 문제에서의 가장 먼저 끝나는 회의 선택)를 각 단계마다 선택하는 건데

회의실 배정 문제 증명 방식을 따로 공부한 뒤, 이 문제의 증명을 어떻게 해야될까 고민해봤는데...

잘 되지 않아서 질문드립니다. (인터넷에도 보면 단순히 "먼저 배송되는 걸 처리하는 게 더 효율적이다." 라는

단순한 말만 나와있지 엄밀한 수학적 증명은 나와있지 않습니다.)

혹시 힌트라도 주실 수 있을까요?

kipa00   3년 전

이 문제는 같은 시간대를 공유하는 회의실이 많은 버전이라고 생각할 수 있습니다. 즉, 1번 마을에서 보내고 2번 마을에서 받는 택배 20개는, 시각 1부터 시각 2까지 진행하는 회의가 20개 있는 것으로 생각할 수 있습니다.

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