[백준] 1300번 : K번째 수 (java)

1300번: K번째 수 (acmicpc.net)

1300번: K번째 수

어떻게 생각하고 문제를 풀었는가?

NxN 배열의 각 원소가 갖는 값은 행 또는 열의 배수로 지정되어 있습니다.

따라서 각 행에서 x보다 작은 값의 개수는 x/i와 N 중에서 작은 값으로 구할 수 있습니다. (x값이 ixN보다 큰 값을 갖는 경우가 존재함)

따라서 B[k]는 x보다 작거나 같은 값을 갖는 원소의 수가 k개 이상인 x를 찾음으로써 답을 구할 수 있을 것이라고 생각하였습니다. 

코드

import java.io.*;

class Main {
    private static int N;
    private static int K;
    public static void main(String[] args) throws IOException {
        readInput();
        int answer = binarySearch();
        System.out.println(answer);
    }

    private static void readInput() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(reader.readLine());
        K = Integer.parseInt(reader.readLine());
        reader.close();
    }

    private static int binarySearch(){
        int left = 1;
        int right = (int) Math.min((long)N*N, 1000000000);
        int result=0;
        while(left <= right){
            int count = 0;
            int mid = (left+right)/2;
            for(int i=1; i<=N; i++){
                count += Math.min(mid/i, N);
            }
            if(count < K){
                left = mid+1;
            }else{
                result = mid;
                right = mid-1;
            }
        }
        return result;
    }
}

이분 탐색으로 작거나 같은 원소가 k개인 x값을 구하는 코드를 작성하였습니다.

1부터 NxN까지의 값에서 적절한 x를 찾기 위해서는 단순한 탐색이 아닌 이분 탐색으로 수행시간을 줄이고자 하였습니다.

left와 right값으로부터 mid 값을 찾아내고, mid 값보다 작거나 같은 원소의 수가 k개 미만일 경우 해당 값보다 큰 값에서 정답이 있으므로 left를 mid+1로 조정, k개 이상일 경우 해당 값보다 작은 값에 정답이 있으므로 right를 mid-1로 조정함으로써 더 빠른 시간 내에 답을 도출해낼 수 있습니다.

문제를 푸는데 있어 주의해야 할 점은 10^9는 2^31보다 작은 값이므로 int를 사용하여도 문제 없지만 NxN 값이 최대 10,000,000,000이므로 long을 사용해야 한다는 점입니다.