kimsd1983   2년 전

Time is Gold...(Time == Gold)

preview

안녕하세요. 시간요정입니다.

다른 어떤 테크닉보다, 이미 M개의 매칭이 완성되는 경우를 찾았는데 남아있는 사람들로 매칭에 되는 경우를 찾아나서면 시간 손해가 매우 큽니다. (수학적 지식이 모자라서 정말 그런지는 확인이 어렵지만, 이 문제의 테케는 확실히 그런 것으로 보입니다. 파이썬3의 경우 시간차이가 3~4배정도입니다.)

사람이 1000명, 일이 500개이고 모든 사람이 모든 일을 다 할 수 있다고 치면, 501번째 사람부터는 탐색이 의미가 없어요.

매칭된 사람의 수가 일의 수와 같아지는 순간 탐색을 끝내면 시간을 많이 많이 많이 아낄 수 있습니다!

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