Sunny Holic

풀이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개의 술 단지를 판독 할 수 있다는 답이 된다.