[BOJ 1300] k번째 수

문제

• BOJ 1300
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

행렬의 원소는 항상 i의 배수가 된다.
이 문제에서 구하고자 하는 것은 K번째에 해당하는 수이므로 K번째 앞에 어떤 숫자가 오든 상관 없이 앞에 몇개가 있는지 생각해주면 된다.

1. k번째 수는 k를 넘지 않으므로 left=0, right=K로 두고 이분탐색을 시작한다.
2. mid값 계산 후, Math.min(mid/i, n)을 누적합한다.
   • 행렬의 원소는 항상 i의 배수이므로 mid/i는 mid보다 같거나 작은 원소의 개수가 된다. mid/i는 최대 n개를 넘지 않으므로 두 경우를 비교해 더 작은 값을 선택한다.
3. 만약 누적합한 결과가 K보다 크거나 같다면 mid 기준으로 왼쪽을 탐색한다. 반대라면, 오른쪽을 탐색한다.

코드

import java.util.Scanner;

public class Main {

    static int N,K;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();

        long left = 1;
        long right = K;
        long mid = 0;
        long Ans = 0;

        while(left <= right){
            mid = (left + right) / 2;
            int cnt = 0;

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

            if(cnt >= K){
                Ans = mid;
                right = mid-1;
            }
            else left = mid + 1;
        }//End 이분탐색

        System.out.println(Ans);

    }
}