BOJ#1300 K번째 수

BOJ#1300 K번째 수

* 문제

https://www.acmicpc.net/problem/1300

* 풀이

- N이 10^5일 때, N*N은 10,000,000,000 이므로 시뮬레이션하여 답을 구하는 것은 시간 내에 불가능합니다.

- 문제를 해결하기 위한 아이디어는 다음과 같습니다.

1. 어떤 수 x가 있을 때, x-1 이하의 수의 개수가 K개 미만이고 x 이하의 수의 개수가 K개 이상인 경우

우리가 찾는 K번째 수는 x 이다.

2. 즉,  x는 x 이하의 수의 개수가 K개 이상이면서 가장 작은 수이다.

3. 위 조건을 만족하는 x를 이분 탐색을 통해 찾는다.

,

그러면 x까지 수의 개수는 어떻게 찾을 수 있을까요?

- N이 4일 때

1 2 3 4

2 4 6 8

3 6 8 12

4 8 12 16

i번째 행은 i의 배수임을 알 수 있습니다.

즉, 각 행에서 x이하의 수의 개수는 min(x/i, N)

,

추가적으로 고려해야할 점

- N이 최대 10^5 이므로 N*N에서 int 범위를 넘어가게 됩니다.

- K가 10^9 이하이므로 이분 탐색에서 right 범위를 좁힐 수 있습니다.

* 나의 코드

https://github.com/stack07142/BOJ/blob/3d1262e7a2aa6b2a715ad8f4a9be56cc9bb50c14/BOJ%231300/src/Main.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {

        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());

        // Solve
        // x를 이분 탐색을 통해 찾는다
        // x : x까지의 수가 k개 이상인 가장 작은 수

        int left = 1;
        int right = (int) Math.min((long) N * N, (long) 1000000000);
        int mid;
        int ans = 0;

        while (left <= right) {

            mid = (left + right) / 2;

            int cnt = getCnt(mid, N);

            if (cnt >= K) {

                ans = mid;
                right = mid - 1;
            } else {

                left = mid + 1;
            }
        }

        System.out.println(ans);
    }

    static int getCnt(int x, int N) {

        int cnt = 0;

        for (int i = 1; i <= N; i++) {

            cnt += Math.min(x / i, N);
        }

        return cnt;
    }
}