독이 든 술 단지를 찾아라

옛날 어느 먼 나라에 술을 매우 즐겨 마시는 왕이 살고 있었다.

어느 날 이웃 나라의 암살자가 창고에 들어가서 술 단지 하나에 독을 넣고 나오다가 붙잡혔다. 

암살자는 어느 단지인지는 모르지만 하나의 단지에만 독을 넣었다고 실토하고는 숨을 거두었다. 

사용된 독의 특징은 식별이 불가능 하며 사람에게만 독성이 있고

독이든 단지의 술을 아주 조금만 맛보아도 술을 맛 본 사람이 자고 일어난 다음날 죽는다.

왕은 독이든 술 단지를 반드시 내일까지 찾아내라고 실력있는 책략가인 당신에게 명하였다.

당신은 투옥된 죄수들을 다음날 살아 남으면 석방을 시켜주는 조건으로 실험에 동원 할 수 있다.

될 수 있으면 최소한의 죄수들을 동원하고자 한다.

창고에 128개의 술 단지가 있고 그 중 하나의 단지에 독이 들어 있을 때

내일까지 독이 든 술 단지를 찾아 내기 위해선 최소 몇 명의 죄수를 동원해야 하는가?

풀이1 -이진법식 풀이-

128개의 술 단지가 있다. 이 128개의 술 단지들에 0~127의 번호를 붙이자.

즉 0~127번중 한 번호를 찾아 내라는 문제이다.

이 문제에서 죄수의 선택지는 마시다 안마시다. 이 두 가지 뿐이다.

또한 결과도 죽는다 안죽는다 이 두가지 뿐이다.

즉 1과 0 두 가지 숫자만으로 표현이 가능하며 자연스레 이진법 문제가 된다.

0~127은 0000000 ~ 1111111로 표기 할 수 있다.

세어보니 7자리 숫자가 나온다. 즉 7명이면 마시다 안마시다로 0~127번의 술 단지 번호를 표현 할 수 있다는 뜻이다.

고로 최소 동원해야 하는 죄수의 숫자는 7명이다.

0번 술단지는 0000000 즉 아무 죄수에게도 먹이지 않고

1번 술단지는 0000001 즉 7번째 죄수에게만 먹이고

75번 술단지는 1001011 즉 첫번째,네번째,여섯번째,일곱번째 죄수에게만 먹이고

127번 술단지는 1111111 즉 모든 죄수에게 먹이는 것이다.

그리고 다음날

2번 죄수만 죽었을 경우 0100000 즉 32번 술 단지에 독이 들어 있다는 뜻이고

모든 죄수가 죽었을 경우 1111111 127번 술 단지에 독이 들어 있다는 뜻이다.

아무도 안 죽었을 경우 0000000 0번 술 단지에 독이 들어 있는 것이다.

풀이2 -난 이진법같은거 모르겠다식 풀이-

한 개의 술단지를 아무도 안먹었을때 아무도 죽지 않으면 그 술 단지는 독이 있는 술 단지이니 일단 거저 1개를 얻는다.

파란색이 술 단지이고 원이 사람이라고 치자.

1명의 사람은 1+1개의 술 단지를 판독 할 수 있다.

2명이 되면 3+1개의 술 단지를 판독 할 수 있다.

3명이 되면 7+1개의 술 단지를 판독 할 수 있다.

여기서 규칙을 알 수 있다.

2명에서 3명이 될 때를 보면 원 두개를 새로운 원 하나가 양분 시키면서

1,2,3이 4,5,6으로 두배가 된다. 그리고 새로운 원 자신의 고유의 숫자(7) 한 개가 추가되고

마지막으로 거저 얻는 술 단지 한 개가 추가된다. 즉 *2+1에 (+1)이 된다.

즉 현 단계에서 판독 할 수 있는 술 단지의 개수는 전 단계의 개수 곱하기 2 더하기 1이다.

써보자

1: 1 (+1=2)

2: 1*2+1 = 3 (+1 = 4)

3: 3*2+1 = 7 (+1 = 8)

4: 7*2+1 = 15 (+1 = 16)

5: 15*2+1 = 31 (+1 = 32)

6: 31*2+2 = 63 (+1 = 64)

7: 63*2+2 = 127 (+1 = 128)

사실 3까지만 써보더라도 2의 제곱 개수를 구하는 문제라는 것을 알 수 있다.

결국 7명이면 128개의 술 단지를 판독 할 수 있다는 답이 된다.

저작자표시비영리변경금지

• 카카오스토리
• 트위터
• 페이스북

'프로그래밍/알고리즘' 카테고리의 다른 글

THE100YEARSWAR 백년전쟁 풀이  (1)	2015.07.30
비트마스크 사용법  (0)	2015.07.27
조합, 이항계수 계산 코드  (0)	2015.07.15
독이 든 술 단지를 찾아라  (1)	2015.07.12
이클립스 유용 플러그인들  (0)	2015.07.07
완전 좌우 대칭인 시간 찾는 문제  (0)	2015.07.06