9-4: NN단표

NN단표 (NNdan.cpp)

 

문제

---

알랩이는 구구단표처럼 NN단표를 만들었다고 한다.

NN단표는 2차원 배열의 모양으로 곱셈 1단부터 N단까지의 값들을 적어놓은 형태이다.

NN단표의 배열을 A라고 했을 때, 배열의 들어가는 수 A[i][j]=i*j이다.(즉, 4행 7열에는 28, 7행 5열에는 35가 들어가 있다.)

알랩이는 N단까지 나온 숫자들 중에서 K번째로 작은 수를 찾고 싶어한다.

이때, 중복되는 여러 수들을 고려한다. 즉 N*N개의 모든 수들 중에서 K번째 수를 구하는 것이다.  

입력

---

첫째 줄에 배열의 크기 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄에 K가 주어진다. K는 N*N보다 작거나 같고, 10,000,000,000보다 작거나 같은 자연수이다.  

출력

---

K번째 원소를 출력한다.

 

예제 입력

3
7

예제 출력

6

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

public class NNDan {
    /**
     * 알랩이는 구구단표처럼 NN단표를 만들었다고 한다.
     *
     * NN단표는 2차원 배열의 모양으로 곱셈 1단부터 N단까지의 값들을 적어놓은 형태이다.
     *
     * NN단표의 배열을 A라고 했을 때, 배열의 들어가는 수 A[i][j]=i*j이다.(즉, 4행 7열에는 28, 7행 5열에는 35가 들어가 있다.)
     *
     * 알랩이는 N단까지 나온 숫자들 중에서 K번째로 작은 수를 찾고 싶어한다.
     *
     * 이때, 중복되는 여러 수들을 고려한다. 즉 N*N개의 모든 수들 중에서 K번째 수를 구하는 것이다.
     *
     * 첫째 줄에 배열의 크기 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄에 K가 주어진다. K는 N*N보다 작거나 같고, 10,000,000,000보다 작거나 같은 자연수이다.
     *
     * K번째 원소를 출력한다.
     *
     *
     *
     *
     * @param args
     */

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long N = Long.parseLong(br.readLine());

        long K = Long.parseLong(br.readLine());

        long result = findKthNumber(N, N, K);


        System.out.println(result);


    }

    public static long findKthNumber(long m, long n, long k) {
        long left=1, right=m*n;
        while(left<=right){
            long mid= (left+right)/2;
            long count = countSmaller(mid, m, n);
            if (count<k) {
                left=mid+1;
            } else{
                right=mid-1;
            }
        }
        return left;
    }

    private static long countSmaller(long mid, long row, long col) {
        long count = 0;
        for (long i = 1; i<= col; i++){
            long temp = Math.min(mid/i, row);
            count += temp;
        }
        return count;
    }


}