| [ Teach ] in KIDS 글 쓴 이(By): guest (fdjskl) <wcl2.kaist.ac.kr> 날 짜 (Date): 2000년 3월 19일 일요일 오후 01시 35분 51초 제 목(Title): [질문]수학 문제입니다. 수학 문제인데요....... 제가 질문을 받았는데 못 풀어서리... 글쩍글쩍 문제는 다음과 같습니다. n 명의 사람이 각각 서로 다른 한가지 사실은 알고 있습니다. 즉, n 명이 한가지씩 모두 n 가지의 사실을 알고 있다는 예기지여. 근데, 어떤 한 사람은 전화 통화로 자신이 아는 사실을 다른 사람에게 모두 알려 줄 수 있습니다. 대신 전화 건 사람은 전화 받은 사람으로부터는 어떠한 사실도 알 수 없습니다. 즉 전화를 건 사람만 사실을 얘기할 수 있다는 것입니다. 이렇게 릴레이 식으로 사실을 전달 할 때 n 명 모두 n 가지 사실을 모두 알게 되는 데 까지 모두 몇 통의 전화 통화가 필요하는지 그 최소값을 구하시오.,...... worst case의 경우 한번 쭉 n 명이 릴레이 식으로 전화를 하고 다시 역방향으로 전화를 쭉 하면 2n-2번의 통화이면 됩니다...... 그럼 답을 알고 계신 분이 계시면 답변주시면 감사하겠습니다. 그럼 이만....... |