| [ QuizWit ] in KIDS 글 쓴 이(By): outsider (하얀까마귀) 날 짜 (Date): 1999년 9월 16일 목요일 오후 06시 08분 57초 제 목(Title): Re: 수다 퀴즈 허걱. 답 쓴 담에 강의 들으며 생각해보니 엉뚱하게 생각하고 있었다는걸 깨달음. -_- n명의 사람들중에서 m명을 뽑아서 나머지 사람들은 적당히 m명에게 자기 정보를 모아주고, m명이 서로 정보를 교환한 뒤, 다시 적당히 나머지 사람들에게 전하는 방식을 쓸 경우에는 2n-4가 역시 최소네요. n명이 이 방법으로 수다를 떠는 최소 전화 수를 An이라고 하면... 1) n-m명이 m명에게 자기 정보를 보내준다. => n-m번 2) m명이 서로 옵티멀하게 정보를 교환해서 완전히 득도한다. => Am 번 3) m명이 1)의 역순으로 다시 정보를 전달한다. => n-m번 1+2+3 = 2n - 2m + Am 번인데, Am - 2m <= 4 라는건 쉽게 증명할 수 있더군요. -- @< //) `//<_ 하얀까마귀 |