BOJ 14435 - 놀이기구 2

문제 링크 https://www.acmicpc.net/problem/14435

문제 소개

놀이기구가 주어지고, 각 놀이기구에 같이 탈 두명이 각각 주어진다. 그 둘이 놀이기구를 타기 위해서는 둘의 키의 합이 제한을 넘어야 한다. 각 날마다 한 명의 키가 1씩 크며 전날에 제한을 만족한 놀이기구가 그 전날 제한을 만족한 놀이기구 수 보다 많다면 키가 1이 더 큰다. 이때 각 날 별로 몇 개의 놀이기구에 대하여 아이들이 제한을 만족하는지 출력하여야 한다. 

문제 풀이

굉장히 재밌는 아이디어의 문제였고, 이 문제를 혼자 생각하지 못하였다. 거의 모든 부분을 이해한 업솔빙 느낌의 문제였다. 그래서 만약 처음부터 생각했다면 어떤 느낌으로 접근해야 맞을지를 생각하여 작성하였다.

일단 $O(QK)$의 풀이를 생각해보자. 그냥 각 날마다 몇개의 놀이기구를 탈 지 확인해보면 된다. 모든 아이들의 키를 저장해 놓고 있으면서 모든 놀이기구를 보면서 각 놀이기구에 대한 제한을 만족했는지 확인하면 $O(QK)$에 이 문제를 해결 할 수 있다.

여기서 우리는 "볼 필요가 없는 조건"에 대해서는 확인을 안하는 것이 목표이다.
일단 제일 먼저 알 수 있는 것은 아이들의 키가 줄지 않기 때문에 한 번 제한을 통과한 놀이기구는 그 이후 항상 그 제한을 만족하게 되고, 더 이상 볼 필요가 없다. 

그러면 우리가 주목해야할 것은 "오늘 막 키가 늘었기 때문에 가능해진 조건들"이라는 것이다. 그리고 어제까지는 불가능했지만 오늘 가능해지는 가능성이 있는 조건은 제 오늘 딱 키가 큰 아이가 같이 탑승하는 조건 뿐이다. 이는 처음에 놀이기구들을 탑승하는 아이별로 묶어놓고, 키가 큰 아이의 묶음만 확인하면 된다. 

하지만 여전히 하루에 확인해야하는 놀이기구의 수는 최악의 경우 아직도 Q개이다. 여기서 작은 관찰을 해보자. 제한이 100인 놀이기구는 1일차에는 절대 탈 수 없다. 사실 49일차까지도 절대 탈 수 없다. 그니까 둘의 합이 전혀 못 미치는 경우에도 확인할 필요가 없다는 것이다.
이를 발전 시켜서 생각해보자. 제한이 P인 조건은 둘 중의 한 명의 키가 P/2이상일때만 유의미해진다. 여기서 좀 더 발전을 시켜보자. 제한이 a이고 둘의 키가 각각 b,c여서 안된다면 b가 b+(a-b-c)/2가 되거나 c가 c+(a-b-c)/2이상이 되어야 제한을 뚫을 수 있는 가능성이 생긴다는 것이다. 즉, 제한까지 남은 양의 절반은 무조건 달성해야 가능성이 생긴다는 것이다.
이 말을 조금 바꿔서 생각하면 제한까지 남은 양의 절반을 달성했을때만 확인하면 된다는 것이고 그 때 마다 확인하면 각 제한 별로 log번만 확인하면 된다. 따라서 전체 시간복잡도는 $O(Qlg(키제한))$ 에 이 문제를 해결할 수 있게 된다.