감그레이

勘ぐれい(감그레이): '의심하여 억측하다' 라는 뜻의 '勘ぐる' 와 회색(グレー)의 합성어

감그레이 왕국에는 세 종류의 사람이 있다. 흰색 옷을 입는 사람은 진실만을 말하고, 회색 옷을 입는 사람은 진실 혹은 거짓을 말하며, 검은색 옷을 입는 사람은 거짓만을 말한다. 감그레이 왕국의 왕은 참된 사람을 좋아하기에 항상 진실만을 말하는 흰 옷을 입은 사람만을 고용하고 싶어한다. 그러나 면접장에 모인 지원자들은 모두 검은색 정장을 입고 있어 왕은 누가 어떠한 색의 옷을 입고 있는지 전혀 알 수 없다. 다행히도 모든 지원자들은 서로 무슨 옷을 입고 있는지 알고 있기에, 왕은 이 난처한 상황을 질문을 통해 해결하고자 한다. 왕은 각 지원자 $i$에게 다음과 같은 질문을 정확히 한 번 한다.

$j$번째 지원자는 흰색/회색/검은색 옷을 입은 사람인가?

왕은 모든 지원자에게 위와 같은 질문을 한 뒤, 흰 옷이 아니라고 판단되는 한 사람을 탈락시킬 수 있다. 탈락자는 더 이상 정장을 입을 필요가 없으므로 옷을 벗고 나가게 되는데, 이때 왕은 그 사람이 실제로 무슨 색 옷을 입었는지 확인할 수 있다. 왕은 탈락자에게는 질문을 할 수 없고, 질문의 대상으로 탈락자를 정할 수 없다. 만약 남아 있는 지원자들이 전부 흰 옷을 입었다고 판단되면 왕은 과정을 멈춘다. 왕의 목표는 흰 옷을 입은 사람만을 남기되, 남은 흰 옷을 입은 사람의 수가 최대이도록 하는 것이다. 왕이 모든 지원자에게 질문하고 응답을 취합해 한 사람을 탈락시키거나 종료하는 절차를 반복할 수 있도록 프로그램을 작성하자.

문제

힌트