[BOJ 18621] Cloyster

문제: https://www.acmicpc.net/problem/18621

 

풀이:

일단 가장 간단한 문제의 성질을 이용한 hill-climbing 풀이를 생각합시다. 한 점을 잡고, 매 번 주위 8칸을 보면서 더 큰 쪽으로 이동합니다. 이 방법으로 답을 찾을 수 있다는 것은 간단하지만 매우 중요하게 사용될 것입니다.

 

답이 있는 영역을 절반으로 줄여봅시다. $(\left\lceil N/2 \right \rceil, *)$ 위치에 대해 쿼리를 날린 이후, 해당 가로줄에 있는 수중 가장 큰 수가 있는 위치 $(\left\lceil N/2 \right \rceil, j)$ 근처의 모든 셀에 대해 쿼리를 날립니다.

• $(\left\lceil N/2 \right \rceil, j)$보다 큰 수가 없을 경우에는 해당 수가 가장 큰 수이기 때문에 답을 찾았습니다.
• 가장 큰 수 $v^*$가 $(\left\lceil N/2 \right \rceil - 1, *)$에 있을 경우, 답의 $x$좌표는 1 이상 $\left\lceil N/2 \right \rceil$미만 입니다.
  
  • $v^*$는 $(\left\lceil N/2 \right \rceil, *)$의 모든 수 보다 더 큽니다.
  • 즉, $v^*$에서 인접한 수를 보면서 더 큰 쪽으로 이동하면, $(\left\lceil N/2 \right \rceil, *)$ 선을 넘을 수 없습니다.
  • 즉, 답의 $x$좌표가 $\left\lceil N/2 \right \rceil$ 보다 작습니다.
• 가장 큰 수가 아래쪽에 있을 때는 마찬가지로 답의 $x$좌표가 $\left\lceil N/2 \right \rceil$ 보다 크다는 것을 알 수 있습니다.

이제 답이 있는 영역을 절반으로 줄일 수 있습니다.

 

 

이것을 한 번 더 같은 방식으로 구현하면 문제가 발생합니다.

• 처음에 쿼리를 날려서 답의 x좌표가 $3$ 미만이라는 것을 알았습니다.
• 이제 $y=3$을 기준으로 쿼리를 날려서, $31$이 해당 줄에서 가장 크다는 것을 알았고, $37$이 $31$보다 크기 때문에 해당 쪽으로 이동합니다.
  • 이 경우 $y = 3 , x < 3$은 넘을 수 없지만, $x=3$을 넘어서 답을 찾을 수 있습니다.

그래서 우리는 경계를 넘을 수 없도록 해야합니다. 해당 영역 안의 값 $v$를 잡아서, 밖의 영역이 항상 $v$보다 작도록 유지합니다. 처음에 $v$는 $(1, 1)$에 쿼리를 날려서 결정합니다.

• 가로줄 하나에 대해서 쿼리를 날립니다.
• 만약 이 가로줄의 최댓값이 $v$보다 작으면, 답은 $v$가 있는 반평면에 존재합니다.
• 만약 이 가로줄의 최댓값 $v^*$ 가 $v$보다 크면 절반으로 나누어서 구분선을 넘지 않는 위 논리를 그대로 적용할 수 있습니다. 새로운 $v$를 $v^*$에 인접한 가장 큰 수로 잡으면 위 구현을 재귀적으로 할 수 있습니다.

$N \times N$ 영역을 가로선 기준으로 잡으면 $N + O(1)$ 만큼, 세로선 기준으로 다시 잡으면 $N/2+O(1)$만큼 쿼리를 날리게 됩니다. 이 경우 영역의 한 변의 길이를 절반 줄이는데 $1.5N+O(1)$가 들기 때문에 총 $3N+O(\log N)$ 번으로 모든 문제를 해결할 수 있습니다.

 

코드: https://www.acmicpc.net/source/share/6f84f099174c40f98c819f9fc1c89255