BOJ 28258 - 초콜릿 보물 찾기
$Q \le 50$ 이므로 홀수나 짝수번째 칸에만 쿼리를 날리는 식으로 생각해볼 수 있다.
만약 어떤 칸에 쿼리 결과로 $1$ 을 받았다면 해당 칸의 주변의 $2 \sim 4$ 칸을 모두 탐색해보고 정답을 낼 수 있다.
그럼 $54$번이면 정답을 알 수 있다.
그런데 $2 \sim 4$ 칸에 모두 날리는게 아닌 $1$번의 칸은 안날리고 나머지 칸들에서 안나왔을 경우 거기서 나온다고 가정하면 $53$번이면 정답을 알 수 있다.
더 줄여보기 위해 $(0,0), (9,9)$ 칸은 날리지 않는다고 생각해보자.
그럼 $51$번이 되고, 여기서 주변이 $4$칸이 비어있는 칸을 먼저 쿼리하고 $3$칸이 비어있는 외곽의 칸들을 그 다음에 쿼리하는 것으로 $50$ 번으로 줄일 수 있다.
만약 이 $48$개의 칸에서 나오지 않았다고 하면 남은 쿼리는 $2$번이다.
이제 여기서 $(0,0)$에 쿼리를 날린다고 해보자.
만약 거기에 존재한다면 $(0,1)$이나 $(1,0)$ 에 마지막 남은 쿼리를 날려 정답을 얻을 수 있고,
$(0,0)$에 없다면 $(9, 9)$엔 무조건 존재한다는 뜻이므로 $(8,9)$에 날려서 거기에 있다면 $(8,9),(9,9)$ 이고 아니면 $(9,8), (9,9)$ 로 딱 남은 두번으로 모든 경우를 검사할 수 있다.
Comments