bj 1300 K번째 수(이분탐색)

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

 

이 문제는 사실 상 이분 탐색 보단, 사고력 문제인 것 같다.

 

8이라는 수가 몇 번째 수인지 확인하기 위해서는

8 / i 라는 것만 알면 쉽게 풀 수 있다.

8 / 1(1단) = 8

-> 1*1, 1*2, 1*3, 1*4, 1*5, 1*6, 1*7, 1*8 이렇게 8개이다.

-> 즉, 1*x <= 8 에서 x의 값이 자신을 포함한 총 갯수이다.

-> 이때, x의 값은 N보다 작아야 한다.

-> cnt += Math.min(mid / i, N); 이라는 식이 이 문제의 핵심이다.

 

이후, 이분 탐색으로 result를 찾아주면 된다.

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

public class Main {
    /**
     * 1,2,3
     * 2,4,6
     * 3,6,9
     * 1,2,2,3,3,4,6,6,9
     */
    static int N, k;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(bufferedReader.readLine());
        k = Integer.parseInt(bufferedReader.readLine());

        int start = 1;
        int end = k;
        int result = 0;
        while(start <= end) {
            int mid = (start + end) / 2;
            int cnt = 0;

            for(int i = 1; i <= N; i++){
                cnt += Math.min(mid / i, N);
            }

            if(cnt >= k){
                result = mid;
                end = mid - 1;
            }else{
                start = mid + 1;
            }
        }
        System.out.println(result);
    }
}