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