백준 1300 K번째 수 Java

이분 탐색으로 분류되어 있는 K번째 수이다.

 

N제한이 100,000에

배열은 N*N인 10,000,000,000으로 굉장히 크다.

그러므로 직접 배열을 만들어서 수를 구한다든지 하는

방법들은 전부 정답이 될 수 없다.

 

이 문제에서 가장 중요한 부분은

배열에 들어가는 수가 A[i][j] = i * j 이기 때문에

i번째 행이나 i번째 열은 i의 배수이라는 점이다.

 

N이 2일 때의 배열을 보자.

1	2	3	4
2	4	6	8
3	6	9	12
4	8	12	16

x라는 수가 있을 때

x가 몇번째로 큰 수 인지 찾기 위해서는

cnt 변수를 두고

i번째 행이나 열이 i의 배수이기 때문에

x / i를 했을 때 N을 넘는다면 N번째 행이나 열보다 전부 큰 것이기 때문에

N을 더해주고

N이 넘지않는다면 x / i를 더해주면 된다.

 

이렇게 x라는 수가 몇 번째로 큰 수 인지 찾을 수 있으면

이분 탐색을 통해 K번째 수를 찾을 수 있다.

다른 이분탐색 처럼

x가 몇 번째 수인지 찾을 때

k번째 수보다는 크고 제일 가까웠던 수를 찾으면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Q1300 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());
        int left = 1;
        int right = k;
        int ans = 0;
        while (left <= right) {
            int 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;
    }
}