K번째 수

• N개의 수가 주어졌을때, X보다 작은 수의 갯수를 세는 것이 O(T)에 가능하다면, K번째 수는 파라메트릭 서치를 이용해서 O(TlogN)에 찾을 수 있다. K번째 수는 'a_1, …, a_N 중에서, a_i보다 작은 수의 갯수가 K-1개 이상인 가장 작은 a_i' 로 표현할 수 있기 때문이다.
  • 이 테크닉을 사용하는 대표적인 다른 예시로 구간 쿼리가 있다. 머지소트트리를 사용해서 X보다 작은 수의 갯수를 O(log^2(n))에 셀 수 있고, 이것을 이진탐색으로 반복해서 O(log^3(n))에 구간 내 K번째 수를 찾을 수 있다.
• 여기서도 같은 방법을 사용한다. i*j로 만들어질수 있는 수 중에서 X보다 작은 수의 갯수를 세는 것은, i를 1,2,…,N으로 증가시키면서 i*j<X인 j의 갯수를 더하는 방식으로 가능하다. i=K일때 이러한 j의 갯수는 min((X-1)/K, N)으로 O(1)에 구할수 있고, 따라서 모든 i에 대한 j의 갯수의 합은 O(N)에 구할수 있다.
  • 살짝 더 효율적으로 하면, i가 [1, X/N] 범위에 있을때는 모든 가능한 j값 [1,N]에 대해서 i*j ⇐ X 가 된다. 따라서, i의 루프를 1~N에 돌릴 필요 없이 (X/N + 1)에서 N까지만 돌리는 것으로 충분하다.
• 답의 범위가 1~N^2 이므로, X보다 작은 수의 갯수를 세는 것을 O(log(N^2)) = O(logN)번 해야 한다. 따라서 총 시간 복잡도는 O(NlogN)
• 구현할때 신경써야 할 부분은 'X보다 작은수의 갯수가 K-1개 이상인 가장 작은 X'를 [1,N^2]의 모든 자연수 중에서 찾았을때, 그 X가 i*j로 표현되는 수라는 보장은 없다. 이것을 처리 하기 위한 간단한 방법은, 'X보다 작은수의 갯수가 K개 이상인 가장 작은 X'를 찾는 것이다. 이렇게 하면 X-1이 i*j로 표현되는 K번째 수가 된다는 것은 쉽게 증명 가능하다.

"""Solution code for "BOJ 1300. K번째 수".

- Problem link: https://www.acmicpc.net/problem/1300
- Solution link: http://www.teferi.net/ps/problems/boj/1300
"""

from teflib import algorithm


def main():
    def is_greater_than_k_nums(num):
        low = (num - 1) // N 
        smaller_num_count = low * N
        smaller_num_count += sum((num - 1) // i for i in range(low + 1, N + 1))
        return smaller_num_count >= k

    N = int(input())
    k = int(input())

    print(algorithm.binary_search(0, k + 10, is_greater_than_k_nums) - 1)


if __name__ == '__main__':
    main()

• Dependency: teflib.algorithm.binary_search