백준 1300번 K번째 수

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

1300번: K번째 수

 

 

처음에는 이분탐색으로 생각하지 못 했습니다.

브루스 포스로 하는 경우 n log(n)이 최대이기 때문에 시간초과 또는 메모리 초과가 나오게 된다.

문제의 배열의 각 원소의 값이 i*j이기 때문에 각 행에서 mid 값보다 작은 값의 개수를 구하기 위해서는 mid / 행을 하면 된다. 이를 통해 mid값이 몇번째 index에 존재하지는 확인할 수 있다.

 

package BOJ;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_1300 {
    static long n;
    static long target;
    static long cal(long mid){
        long cnt = 0;
        for(long i = 1; i <= n; i++){
            cnt += Math.min(n,mid/i);
        }
        return cnt;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Long> stol = Long::parseLong;
        n = stol.apply(st.nextToken());
        st = new StringTokenizer(br.readLine()," ");
        target = stol.apply(st.nextToken());
        long start = 1;
        long end = n*n;
        long result = 1;
        while(start <= end){
            long mid = (start + end) / 2;
//            System.out.println(mid+" "+cal(mid));
            if(cal(mid) >= target) {
                result = mid;
                end = mid - 1;
            }else{
                start = mid + 1;
            }
        }
        System.out.println(result);
    }
}