[백준] 1300번 K번째 수

문제 설명

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

문제 풀이

• 이분탐색을 이용하여 풀이하였다.
• 이분탐색의 대상은 몇번째인지가 아닌 어떤 수인지이며 해당 수를 이용하여 다음을 판별하였다

  • Count(int n) //해당 수보다 같거나 작은 수의 갯수
  • Count(mid - 1) 번째 보다 작거나 같은 경우 -> hi = mid;
  • Count(mid) 번째보다 큰 경우 -> lo = mid;
  • 이외의 경우 -> mid값 리턴

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

public class Main{
    public static BufferedReader br;
    public static BufferedWriter bw;
    public static int N, M;

    public static long calCount(long n) {
        long result = 0;
        for (int i = 1; i <= N; i++)
            result += Math.min(N, n / i);
        return result;
    }

    // M이 해당 숫자 범위 일때 : 0
    // M이 해당 숫자 범위 보다 낮을 때 : -1;
    // M이 해당 숫자 범위 보다 높을 때 : 1;
    public static int cal(long n) {
        long low = calCount(n - 1);
        long high = calCount(n);
        if (M <= low) return -1;
        else if (M > high) return 1;
        else return 0;
    }

    public static long solve() {
        long lo = 1;
        long hi = (N * (long)N + 1);
        while (lo + 1 < hi) {
            long mid = (lo + hi) / 2;
            if (cal(mid) == 0) return mid;
            else if (cal(mid) == -1) hi = mid;
            else lo = mid;
        }
        return lo;
    }

    public static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        bw.write(solve() + "\n");
        bw.flush();
        br.close();
        bw.close();
    }
}