boj_3020_개똥벌레

https://www.acmicpc.net/problem/3020 <풀이> 가장 먼저 브루트포스로 어떻게 풀 수 있을지 생각해보았다. 각 높이 h 마다 몇개의 장애물이 존재하는지 탐색해본다면, O(NH)의 시간복잡도가 필요하다.

하지만 NH는 10^11으로 1초안에 불가능하다. 따라서 1초안에 해결하기 위해서는, N 혹은 H의 시간복잡도를 O(log)로 줄여아, O(NlogN)풀이가 가능해진다.

그럼 N과 H중 뭐를 O(log)로 줄일 수 있을까? 우선 N은 줄일 수 없다고 생각했다.

왜냐하면, 석순or종유석의 높이가 다양하고, 이분탐색을 하기위한 어떤 규칙이 안 보였기 때문이다. (Search Space를 줄였을 때, 정답이 이 공간에 무조건 존재하는 규칙) 그래서 모든 N에 대하여, H..........