[백준] 1300번 - K번째 수 (Gold 2)

문제 링크

백준 1300번 - K번째 수 (Gold 2)

문제 설명

N 이하의 두 자연수의 곱으로 쓸 수 있는 자연수 중 K번째로 작은 수를 출력한다.

주의점

제한시간이 2초이고 $N \leq 10^5$이므로, 대략 $2 \times 10^8$ 정도의 연산이 허용된다.
따라서 $O(N^2)$ 이상의 시간복잡도를 가지는 알고리즘을 사용해서는 안 된다.

정답코드 및 설명

M 이하의 자연수 중 N 이하의 두 자연수의 곱으로 쓸 수 있는 자연수의 개수를 $\textrm{underM}(M)$이라 하자(중복을 포함하여 센다).
$\textrm{underM}(M) \geq k$인 최소의 k는 $\textrm{underM}(M) < k$인 최대의 k에 1을 더한 값과 같다.
$\textrm{underM}(M) \leq k$인 최대의 k를 구해서는 안된다.
반례로, N = 3, k = 7이 있다. $\textrm{underM}(5) = 6$, $\textrm{underM}(6) = 8$인데, 7번째로 작은 수는 5가 아닌 6이다.

이제 $\textrm{underM}(M)$만 계산할 수 있다면 이분탐색을 통해 문제를 해결할 수 있다.
M 이하의 자연수 중 i와 N 이하의 자연수의 곱으로 쓸 수 있는 자연수의 개수는 $\textrm{min}(M/i, N)$이다.
또한, k번째 수는 항상 $\textrm{min}(\lceil\sqrt{k}\rceil^{2}, N)$ 이하이다.
문제 해결에 꼭 필요하지는 않지만, 탐색 범위를 조금이라도 줄일 수 있다.

시간복잡도는 $\textrm{underM}(M)$의 계산에 O(N)이 소요되고, 이분탐색 과정에서 $\textrm{underM}(M)$을 $O(\log N^{2}) = O(\log N)$회 계산하므로 $O(N\log N)$이다.

import java.io.*;
    
public class Main {

    static long N;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        long k = Integer.parseInt(br.readLine());
        bw.write(answer(k) + "");
        bw.close();
    }

    static long answer(long k) {
        long i = 0;
        while (i * i < k)
            i++;
        long max = i * i + 1;
        long min = 1;
        long mid;
        while (min + 1 < max) {
            mid = (max + min) / 2;
            if (underM(mid) >= k)
                max = mid;
            else
                min = mid;
        }
        if (underM(min) != k)
            min++;
        return min;
    }

    static long underM(long m) {
        long underM = 0;
        for (int i = 1; i <= N; i++) {
            underM += m / i <= N ? m / i : N;
        }
        return underM;
    }
}