JHB의 프로그래밍 삽질기

퀴즈5 와인 1000개에서 독이 든 와인 찾기. 본문

PROGRAMMING/Algorithm

퀴즈5 와인 1000개에서 독이 든 와인 찾기.

roter 2011.08.04 14:21



뿅뿅나라 왕은 와인 매니아 입니다. 창고에 와인이 1000병이나 있지요.
어느날 뿅뿅나라 왕은 VIP들을 초대하여 와인 1000병을 모두 파티에 사용하려 합니다.

아뿔싸! 이웃나라의 스파이가 와서 와인 한병에 독을 주입했어요. 딱 한병에만 독을 넣었다는데, 어느 병에 넣었는지 절대로 알 수가 없습니다. 그리고 독은 맹독이라, 와인에 섞인 독을 마시면 즉사하게 됩니다.
왕은 슬퍼하며, 금세기 최고의 탐정 겸 소믈리에인 당신을 부릅니다. 독이 섞인 와인 한병을 찾아달라구요.

매우 끔찍하고 무서운 얘기지만, 왕은 당신에게 사형수 10명을 주었습니다. 10명을 다 죽여도 좋으니까 독이 든 와인 한병을 걸러 달라는 얘기지요.
자, 10명을 이용해서 독이 든 와인을 찾아 낼 수 있을까요?

조건은 아래와 같습니다.

1) 이미 와인을 마신 사람에게는 독이 든 와인이 효과가 없습니다. 즉, 한번 와인을 먹고 또 다시 와인을 먹고를 반복해봤자, 이미 와인을 마신 상태이기 때문에 독이 든 와인을 마셔도 죽지 않습니다.

2) 독은 매우 강한 맹독이므로 아무리 희석시켜도 효과가 있습니다. 즉 독이 든 와인 1병과 독이 안든 와인 999병을 섞어서 마실 경우, 죽게 됩니다.

3) 초대한 VIP들에게 미리 와인을 한입씩 마시게 하면 독이 효과가 없어질테니 그렇게 하면 되지 않느냐구요? 그건 안됩니다. 그러면 이건 퀴즈가 아니니까요.

자, 사형수 10명으로 독이든 와인을 찾아낼 수 있을까요?





답은 아래로 내리면 있습니다.














답)

없습니다..
는 농담이구요.
답이 두개 있습니다. 우선 한개
병을 500병 500병 두 그룹으로 나누고 조금씩 따라서 섞습니다. 그리고 사형수 한명을 불러서 두 그룹중 한 그룹을 마시게 합니다. 만약 그 사형수가 죽으면 그 500명 중에 있는거고 안죽는다면 남은 500병 중에 있겠죠? 만약에 사형수가 와인을 마시고 죽지 않았다고해도, 그 사형수를 계속 쓸 수는 없습니다. 왜냐면 이미 와인을 마셨기 때문에 독이 효과가 들지 않기 때문이죠.
이제 남은 사형수는 9명. 남은 병은 500명입니다.
이를 250병, 250병 두 그룹으로 나누고 반복합니다. 그럼 병은 250병이 남고 사형수는 8명이 남습니다.
이를 반복합니다.
125병, 7명
63병, 6명
32병, 5명
16병, 4명
8병, 3명
4병, 2명
2병, 1명
마지막에 2병이 남고 1명의 사형수가 남았으니 마지막 남은걸 먹여보면 답을 알 수 있겠죠? 그것이 정답입니다.

자 이제 두번째 정답입니다. 이는 컴퓨터 싸이언스를 전공한 분만 보길 권장합니다.
병에 1번부터 1000번까지 번호를 매깁니다. 그리고 사형수 10명을 일렬로 세웁니다. 1부터 10까지요. 쉽게, 1번 부터 10번 까지 세운다고 칩시다.(제일 왼쪽이 10, 제일 오른쪽이 1)
이제 1000병을 2진수로 변환시켜서, i 자릿수가 1인 와인을 모두 섞어서 ( 9 - i )번재 사형수에게 먹입니다.
즉 512는 2진수로 10 0000 0000 이므로 10번째 사형수는 512번 와인이 섞인 혼합물을 먹게 될 겁니다.
513은 2진수로 10 0000 0001 이므로 1번째 사형수와 10번째 사형수가 513번 와인이 섞인 혼합물을 마시겠죠? 그럼 죽은 사형수를 2진수로 쳐서 이를 10진수로 변환했을 때의 번호 와인에 독이 든 겁니다.
예를 들어서
24는 2진수로 00 0001 1000 입니다. 만약 24번 와인에 독이 들어있다면 4번째 사형수와 5번째 사형수가 혼합와인을 마시고 죽겠죠?

설명하고 나니 무지 어렵네요 -.-;; 설명하기 조차 힘드네요.. 힘들면 첫번째 정답만으로도 이해가 충분히 되실거에요...ㅋ.ㅋㅋㅋ 그럼 이만~
Tag
,
0 Comments
댓글쓰기 폼