BOJ 1300 k번째 수

원래 적을 생각이 없었는데, 시간초과에 좀 이해되지 않는 점이 있어서 일단 적어놓는 김에 풀이도 적어보려고 한다.

이 문제는 n이 10의 5제곱으로 주어져 있지만 문제를 풀기위한 N은 무려 10의 10제곱에 달해서... O(N)의 quick selection도 쓸 수 없다.
난 배열을 그려놓고 나름 규칙을 찾아보겠다고 했는데... 음 사실 어떻게든 문제 유형에 적혀있는 이분탐색에 끼워 맞춰보려 했지만 내 능력 부족으로 별 다른 소득이 없던 차에 스터디 단톡방에서 sksdong님이 문제 풀이를 알려주셨다.

임의의 수 x가 있으면, x이하인 수의 개수가 k과 같거나 크고, x-1이하인 수의 개수가 k보다 작으면 바로 x가 k번째 수가 된다는 것이 이 문제의 핵심이고, x는 이분 탐색을 통해 적절히 찾아나간다.
근데 x이하인 수의 개수나 x-1이하인 수의 개수는 어떻게 구하는가? 한 행을 보면 1행은 1*1, 1*2, 1*3... 2행은 2*1, 2*2, 2*3, ... 이렇게 a행은 a의 배수로 이루어져 있어서, a행에서 x이하인 수의 개수는 min(x/a, n)이 된다. 그리고 총 n행으로 이루어져 있으므로 O(n)만에 x이하인 수의 개수를 구할 수 있다.
이분탐색은 nlog n^2 즉, log 10^10이므로 10^5 * log 10^10 으로 1초안에 충분히 들어오는 걸로 보여지는데...

나는 계속 시간초과를 받았다... 나는 코드에서 x-1이하인 수의 개수가 k보다 작고, x이하인 수의 개수가 k와 같거나 클 경우 그 때의 mid값을 답으로 하고 while문을 break하는 코드를 넣었었는데, 그것을 주석처리하고 x이하인 수의 개수가 k이상인 경우 답을 update해주었더니 시간초과가 안뜨고 맞았습니다를 받았다.

왜 그런지 이해가 안가서, 그냥 코드를 조금씩 변형해보면서 계속 제출을 해봤는데, 일단 내가 얻은 결론은 if문이 하나라도 더 들어가면 수행 시간이 느려지거나 시간초과가 뜨는 것 같다. x-1이하인 수의 개수가 k보다 작으면 답을 다 구한 것이므로 그냥 break하는 if문 하나를 넣는데도 시간초과가 난다... min을 안 쓰고 if문으로 처리해줬더니 시간이 더 오래걸리거나 시간초과가 났다...

그리고 수행시간이 짧은 고수 분들의 코드를 봤는데, long long을 int로 바꾸면 시간이 확 줄어든다. long long을 int로 바꿔도 되는 이유는 바로 k의 제한 때문이다. k는 최대 10의 9제곱 즉 10억이다. 결국 구하는 값의 최대값도 10의 9제곱을 넘을 수 없고, 이분 탐색할 때, r=1e9로 놓고 해도 된다.