내가 지금까지 풀었던 문제 중에 단연코 세 손가락 안에 들 정도로 정말 정말 좋은 문제라고 생각한다. 어떻게 이런 문제가 고등학교 교내 대회에 나왔는지 의문이다. 완전히 내가 푼 것은 아니고 업데이트 횟수를 줄이는 것이 핵심 아이디어라는 힌트를 보고 문제를 해결하였다.
이 문제는 자라는 키를 변화시켜서 온라인 처리를 강제했다. 따라서 나이브한 풀이를 생각해 본 후 최적화를 고민할 것이다. 모든 날짜에 모든 질문을 확인한다면 $O(KQ)$에 문제를 해결할 수 있다. 모든 질문을 확인하는 것이 비효율적이므로 가능한 후보들을 줄이는 방법을 고민해 보자.
두 아이의 키의 합이 $k$이상이려면 어떤 조건이 필요할지 생각해 보자. 둘 중 하나의 키는 $k \over 2$ 이상이어야 한다. 어쩌면 당연하게 보일 수 있는 이 관찰을 이용하면 문제를 해결할 수 있다. 어떤 시점에 둘의 키를 보고 불가능하다는 것을 확인했다고 하자. 이때, 남은 키를 $h$라고 하면 둘 중 하나의 키가 $h \over 2$가 되기 전에는 확인할 필요가 없다. 이런 식으로 확인 횟수를 줄일 수 있다. 한 번 확인할 때마다 남은 키가 절반 이상 줄어들기 때문에 질문 하나 당 $O(log(h))$의 시간이 소요된다. 따라서 전체 시간복잡도는 $O(Qlog(h))$이 될 것이다.
구현은 set을 이용하면 된다. 이 문제와 같은 아이디어를 사용하는 문제로 18473번이 있는데, 무려 루비 문제이다. 이 문제의 풀이를 알고 있다면 충분히 해결할 수 있으니 도전해 보자.
