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




코드

///NN단표

import java.util.*;

public class Main {

    public static ArrayList<Integer> box = new ArrayList<>();
    public static long result = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int b;
        long[][] c;
        int d = 0;
        int max = Integer.MIN_VALUE;

        a = sc.nextInt();
        b = sc.nextInt();


        findNNumber(1, a * a, a, b);

        System.out.println(result);

        sc.close();

    }

    public static void findNNumber(long s, long e, long arr, long b) {

        if (s > e) return;
        else {
            long mid = (s + e) / 2;
            long cnt = howManySmaller(arr, mid);

            if (cnt < b) findNNumber(mid + 1, e, arr, b);
            else {
                if (result > mid) result = mid;
                findNNumber(s, mid - 1, arr, b);
            }
        }

    }

    public static long howManySmaller(long arr, long target) {
        long result = 0;
        for (int i = 1; i <= arr; i++) {
            if (target / i > arr) result += arr;
            else result += target / i;
        }

        return result;

    }

}