[Java] 백준 1300 K번째 수 (이진탐색)

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

 

이 문제는 겉보기에는 단순히 k번째 수를 구하는 문제처럼 보이지만, 실제로는 정렬을 직접 하면 안 되는 문제다.

 

 

N이 최대 100,000이기 때문에 배열 B의 크기인 N²은 최대 10¹⁰이 된다.

 

그래서 배열을 직접 정렬하는 대신, “어떤 값 X 이하의 수가 몇 개인가?”를 세는 방식으로 생각해야 한다.

 

특히 X를 증가시키면 X 이하의 개수는 절대 줄어들지 않는다는 점에 주목해야한다.

즉, 작은 X에서는 k개보다 적다가, 어느 순간부터는 k개 이상이 되고, 그 이후로는 계속 k개 이상이 된다.

 

정리하자면 값 기준으로 개수를 세고, 그 개수의 단조성을 이용해 이진탐색으로 답을 구하는 문제다.

 

이진탐색의 단조성은 아래 글에서 자세히 기술하였다.

[Java] 백준 2343 블루레이 만들기 (이진탐색)

 

---

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        
        long start = 1, end = k;
        long result = 0;
        
        while (start <= end) {
            long mid = (start + end) / 2; 
            long cnt = 0;
            
            // 중간 값보다 작은 수는 몇 개인지 계산
            // i번째 행은 i의 배수이므로
            // 즉 i번째 행에서 mid 이하의 개수는 mid를 i로 나눈 값
            // 단, 한 행에는 최대 N개만 있으므로 Math.min(mid / i, N) 더한다
            for (int i = 1; i <= n; i++) {
                cnt += Math.min(mid / i, n);
            }
            
            // cnt가 k보다 작으면
            // mid는 작으니 start 를 mid + 1로 증가
            // cnt가 k 이상이면
            // mid는 K번째 수가 될 가능성이 있으므로
            // 우선 result에 저장
            // 그리고 더 작은 값이 있는지 확인하기 위해 end를 mid - 1로 감소
            if (cnt < k) {
                start = mid + 1;
            } else {
                result = mid;
                end = mid - 1;
            }
        }
        System.out.println(result);
    }
}