3020. 개똥벌레

작년에 봤을 때 어려워 보여서 스킵했던 문제이다. 기말고사로 스터디 쉬는 동안 풀어보려고 다시 붙잡았는데, 예상 외로 오래 걸렸다. 한 2주 넘게 생각한듯. 내가 이런 문제에 취약한 건가, 겨우 골드5인데..

3020번: 개똥벌레

---

이분 탐색이라는 생각이 들긴 했다. 개똥벌레가 높은 구간을 지날수록 파괴해야 하는 석순의 개수는 (일반적으로) 감소한다. 하지만 높은 구간을 지나는 개똥벌레는 (일반적으로) 더 많은 종유석을 파괴해야 한다. 따라서 개똥벌레가 $i$번째 구간으로 지나갈 때 파괴해야 하는 장애물의 수는 일반적으로 복잡한 형태를 띠게 된다. 예컨대 이차함수처럼 감소하다 증가하는 모양이 아니라는 것이다.

 

그렇다면 어떻게 해야 하는가? 답에 뚜렷한 경향성이 없으므로 모든 구간에 대해 부숴야 하는 장애물의 수를 구해야 한다. $H$가 최대 $500,000$이므로 각 높이마다 로그 시간 안에 계산을 완료해야 한다.

 

나는 처음에 석순과 종유석을 합한 값을 찾으려고 했는데, 그러다 보니 문제가 복잡해졌다. 그런데 오늘 누워있다가 나한테만 놀라운 해답을 알아냈다. 석순과 종유석을 따로따로 생각하는 것이다.

 

개똥벌레가 $i$번째 구간을 지날 때는 길이가 $i$ 이하인 석순을, $h-i+1$ 이하인 종유석을 모두 파괴해야 한다. 그런데 정렬된 배열에서 $i$보다 작은 수의 개수는 이분 탐색으로(여기서는 ``lower_bound()``) 쉽게 구할 수 있다. 따라서 모든 $1 \le i \le H$에 대해 길이가 $i$ 이하인 석순과 $h-i+1$ 이하인 종유석의 개수를 합하여 저장해 놓고, 합의 오름차순으로 정렬하면 정답을 구할 수 있다.

 

# 석순과 종유석의 높이 배열을 정렬해도 정답은 바뀌지 않는다. (펼치기)

석순 또는 종유석의 길이가 중요하지, 순서는 중요하지 않다. 순서가 바뀐다고 해도 부숴야 할 장애물은 어쨌든 부숴야 하기 때문이다.

 

참 쉽죠?

하지만 난 그 쉬운 생각을 못 했지..

---

1년동안 못 풀던 문제 해결. 마냥 기쁘진 않지만.