BOJ 28258 - 초콜릿 보물 찾기

image.png

Q50Q \le 50 이므로 홀수나 짝수번째 칸에만 쿼리를 날리는 식으로 생각해볼 수 있다.

만약 어떤 칸에 쿼리 결과로 11 을 받았다면 해당 칸의 주변의 242 \sim 4 칸을 모두 탐색해보고 정답을 낼 수 있다.

그럼 5454번이면 정답을 알 수 있다.

그런데 242 \sim 4 칸에 모두 날리는게 아닌 11번의 칸은 안날리고 나머지 칸들에서 안나왔을 경우 거기서 나온다고 가정하면 5353번이면 정답을 알 수 있다.

더 줄여보기 위해 (0,0),(9,9)(0,0), (9,9) 칸은 날리지 않는다고 생각해보자.

그럼 5151번이 되고, 여기서 주변이 44칸이 비어있는 칸을 먼저 쿼리하고 33칸이 비어있는 외곽의 칸들을 그 다음에 쿼리하는 것으로 5050 번으로 줄일 수 있다.

만약 이 4848개의 칸에서 나오지 않았다고 하면 남은 쿼리는 22번이다.

이제 여기서 (0,0)(0,0)에 쿼리를 날린다고 해보자.

만약 거기에 존재한다면 (0,1)(0,1)이나 (1,0)(1,0) 에 마지막 남은 쿼리를 날려 정답을 얻을 수 있고,

(0,0)(0,0)에 없다면 (9,9)(9, 9)엔 무조건 존재한다는 뜻이므로 (8,9)(8,9)에 날려서 거기에 있다면 (8,9),(9,9)(8,9),(9,9) 이고 아니면 (9,8),(9,9)(9,8), (9,9) 로 딱 남은 두번으로 모든 경우를 검사할 수 있다.

Tags:

Categories:

Updated:

Comments