[BOJ] K번째 수

K번째 수

문제

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

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

입력

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

출력

B[k]를 출력한다.

예제 입력

3
7

예제 출력

6

풀이

역시나 이진탐색을 하는 방법이 어려운 것이 아니라 어떻게 적용해서 푸는지가 정말 어려운 것 같다.. 처음에 행렬을 반으로 쪼개고 개수를 세고.. 많이 생각했지만 뭔가 접근 방법이 틀렸을 것 같다는 생각이 들어 결국 구글링을 하였다.

K번째 수를 찾기 위해서, K보다 작은 숫자의 개수를 세는 것이다. 그러기 위해서는 K / i 를 해야 한다. (i는 행)

예를 들어 N = 3, K = 7인 경우 7보다 작은 숫자의 개수를 찾고 싶다면 다음과 같다.

1 2 3 --> 7/1 = 7 인 경우(n보다 큰 경우)는 없기 때문에 min(n, k/i) 값인 3 이 된다.

2 4 6 --> 7/2 = 3

3 6 9 --> 7/3 = 2

위와 같은 방법으로 low = 1, high = 7(k)로 이진 탐색을 진행한다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int low = 1;
        int high = k;
        int result = 0;

        while (true) {
            if (low > high) {
                break;
            }
            int mid = (low + high) / 2;
            int cnt = 0;
            for (int i = 1; i <= n; i++) {
                cnt += Math.min(mid / i,n);
            }

            if (cnt < k) {
                low = mid + 1;
            } else {
                result = mid;
                high = mid - 1;
            }
        }
        System.out.print(result);

    }
}