이것도 전형적인 이분탐색 문제인데 아무리 생각해도 시간 복잡도가 O(N^2 logN)으로 시간이 10^8을 넘어 시간 초과가 뜨지 않을까 제출 전에 계속 고민했었다. 근데 아무리 고민해도 시간 복잡도를 더 줄일 수가 없을 것 같아 혹시나 해서 이대로 제출했더니 통과해버렸다..
풀이를 검색해보니 다른 사람들도 시간 복잡도가 나와 같았는데 1억을 넘어도 시간 초과를 안하고 통과할 수도 있다는 걸 처음 알았다. 지금까지는 1억 넘으면 무조건 시간 초과인줄 알았는데... 시간 복잡도가 애매하고 더 줄이기 힘들어보이면 일단 제출하고 봐야되나보다.. 암튼 새로운 사실을 알아서 기쁘다!
아 그리고 여기서 정답이 되는 cnt값을 int가 아닌 long long으로 지정해주었는데, 이유는 최대 10000C3이 될 수 있기 때문에 int 범위를 벗어날 수도 있기 때문이다. 실제로 int로 제출했을 때 한 40% 정도에서 틀려버렸다