본문 바로가기

프로그래밍/알고리즘

독이 든 술 단지를 찾아라

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

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

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

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

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

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

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

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


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

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