1300번: K번째 수

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

문제

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 10^5보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(10^9, N^2)보다 작거나 같은 자연수이다.

출력

B[k]를 출력한다.

예제 입력 1

3
7

예제 출력 1

6

풀이

package binary_search;

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

public class Main_1300 {

    private static long n;
    private static long k;
    private static long result;

    public static void main(String[] args) throws IOException {
        input();
        process();
        output();
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
    }

    private static void process() {
        binarySearch(1, n * n);
    }

    private static void binarySearch(long start, long end) {
        long mid = (start + end) / 2;

        if (start > end) {
            return;
        }

        if (isRight(mid)) {
            result = mid;
            end = mid - 1;
        } else {
            start = mid + 1;
        }

        binarySearch(start, end);
    }

    private static boolean isRight(long mid) {
        long count = 0;

        for (int i = 1; i <= n; i++) {
            long temp = mid / i;

            if (temp > n) {
                temp = n;
            }

            count += temp;
        }

        return count >= k;
    }

    private static void output() {
        System.out.println(result);
    }
}