백준 1300번: K번째 수

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

NxN 배열 A에 A[i][j]=ixj 일때, 일차원 배열에 배열의 값들을 오름차순으로 정렬하여 넣었을 때, K번째 수를 구하는 문제이다.

처음에는 그냥 배열을 만들려고 했지만 N이 10^5 까지 들어오기 때문에 불가능하다. 그러므로 K번째 수를 앞에 몇개의 수가 있는지 이분탐색을 통해 찾아가야 한다.

 

i행에서 특정 숫자 x보다 작거나 같은 수의 갯수는 i x j <= x를 만족해야 하므로 j <= x/i 이므로 x//i 가 된다. 각 행에서 이 조건을 만족하는 수의 갯수의 합이 x의 위치이며 이 갯수가 K보다 크면 K번째 숫자보다 x가 작거나 같음을 의미하고, K보다 작으면 x가 K번째 숫자보다 크다는 것을 의미한다. 따라서 이분탐색이 끝날 때 까지 갯수가 K보다 크거나 같을 때 마다 K번째 수를 계속 갱신해주면 된다.

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

public class k번째수1300 {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());
        long k = Long.parseLong(br.readLine());
        br.close();
        long start = 1, end = k;
        long answer = 0;
        while (end >= start) {
            long mid = (start + end) / 2;
            long count = 0;
            for (long i = 1; i <= n; i++) {
                count += Math.min(n, mid / i);
            }
            if (count >= k) {
                end = mid - 1;
                answer = mid;
            } else {
                start = mid + 1;
            }
        }
        System.out.print(answer);
    }
}