| [ QuizWit ] in KIDS 글 쓴 이(By): whinii (휘니군) 날 짜 (Date): 2003년 11월 10일 월요일 오후 08시 12분 33초 제 목(Title): 정치인 문제 사실은 풀고 있는 문제인데, 마땅한 해법이 생각나질 않아서..=.= 여기에 포스팅합니다. :) n명의 정치인이 있습니다. 이들을 4일 동안 연속으로 열리는 파티에 초대하려 하는데, 각 정치인을 4일 중 하루를 택해 초대하려 합니다. 그런데 이 정치인들 간에는 서로 사이가 안 좋은 정치인들도 있습니다. 이들은 자기 감정을 제어 못하기 때문에, 사이가 안 좋은 정치인 둘을 같은 날 파티에 초대했다간 싸워서 파티를 전부 망쳐 버릴 것입니다. 그렇기 때문에, 사이가 안 좋은 정치인의 any pair 도 한 날에 초대하지 않으면서 모든 정치인이 한번씩 파티에 다녀갈 수 있는 일정이 있을까요? 이때 정치인의 수 n <= 300, 사이가 안 좋은 정치인 pair 의 수 m <= 5000 입니다.. 답이 과연 brute-force backtracking 밖에 없을지 궁금하네요. 싫어하는 정치인의 수가 많은 쪽부터 배정하는 방식으로 분기한정을 해보려는데 여의치가 않아서요. 혹자는 다음과 같은 greedy method 를 제시하기도 하던데 정당성을 증명할 수가 없더군요. a. make all the politicians available b. for each of the four days 1. consider an empty list (L) of politicians for that day. 2. add the first available politician to L. 3. for every other available politician, add him/her in L only if s/he is in good terms with all the politicians already in L. 4. make all the politicians in L unavailable 그러니깐 묻고 싶은 것은, 1) 이 문제에 대해 다항시간 해법이 있을까요? 2) 저 greedy method 는 옳을까요, 틀릴까요? 입니다. 퀴즈가 아니라 질문 같아서 죄송하네요. 그래도 생각 나시면 답변 주세요. :) -JongMan :: whinii the fantast : whinii@diva.yonsei.ac.kr : http://whinii.com/tm/ |