75단계 만에 실격을 피하는 법
시간 제한1초메모리 제한1024 MB
1000개 위치 중 두 명의 위원장을 찾는 문제입니다. 로봇은 한 번만 보낼 수 있고, 지정한 위치에 위원장이 한 명이라도 있는지만 알려 줍니다. R대의 로봇으로 H시간 안에 두 위치를 찾습니다.
문제
당신은 열린 금고 앞에 서 있고, 손에는 메달이 들려 있다. 하지만 주변을 둘러보자 기쁨은 금세 사라진다. 방에서 찾은 넥타이에 적힌 메시지에 따르면 조수가 당신의 계획을 과학위원회에 알린 것이다! 이제 두 명의 위원장이 건물 안에 숨어서 당신의 탈출을 막으려 한다.
다행히 다른 참가자들과 거래하고 남은 진공청소기 로봇 대가 있다. 이 로봇으로 두 위원장의 위치를 찾아내면 탈출하는 동안 그들을 피할 수 있다. 각 로봇에게 위원장이 있을 수 있는 개의 위치 중 여러 곳을 정찰하도록 지시할 수 있다. 안타깝게도 로봇의 소프트웨어는 매우 단순하다.* 각 로봇은 정찰한 위치 중 적어도 한 명의 위원장이 있는지만 감지할 수 있다.
각 로봇은 정찰을 끝내고 결과를 가지고 돌아오기까지 꼬박 한 시간이 걸린다. 이 과정에서 로봇의 배터리가 많이 소모되므로 각 로봇은 한 번만 보낼 수 있다.
저녁 행사에 늦고 싶지 않으니, 최대 시간 이내에 위원장들의 위치를 알아야 한다. 특히 앞서 보낸 로봇이 돌아오기를 기다리지 않고 여러 로봇을 한꺼번에 보내야 할 수도 있다. 두 위원장은 시간이 지나도 같은 위치에 머문다고 가정해도 된다.\†
이 정찰 임무를 계획하고 두 위원장이 어디에 있는지 알아내는 프로그램을 작성하라.
* 어차피 좋은 로봇은 다른 참가자들에게 다 팔아 버렸으니까!
\† 늦은 밤까지 준비 작업을 하느라 위원장들은 너무 지쳐서 움직이지도 못한다.