백준 1300. K 번째 수 - JAVA, 이분 탐색

 

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

 

 

 

 

코드 & 풀이

 

import java.io.*;

public class 백준_K번째수_1300 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());

        int low = 1;
        int high = K;
        int answer = 0;

        while (low <= high) {
            int mid = (low + high) / 2;
            long count = 0;

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

            if (count < K) {
                low = mid + 1;
            } else {
                high = mid - 1;
                answer = mid;
            }
        }

        System.out.println(answer);
    }
}

 

 

    i * j 연산을 한 후에 정렬을 하면 답은 나오겠지만, 시간을 초과하겠죠?
    
    찾아보니까 이분탐색을 하라네?
    
    그래서 어떻게 할까 하고 보니
    
    N * N 표를 그려보니
    
    오른쪽 최상단 (0, N-1), 왼쪽 최하단(N-1, 0) 을 이었을 때를 기준으로 작거나 큰 것을 볼 수 있었음.
    
    그래서 그 갯수를 기준으로 row, high를 움직이면서 정답을 찾아가면 됩니다.
    
   ps. 처음에 high를 N * N으로 놨는데 틀림
    
    1. K 번째의 수는 K를 넘길 수 없는데 굳이 N * N으로 설정할 이유가 없음.
    
    2.이렇게 되면 K를 넘는 수가 후보로 탐색되면서 의도치 않은 결과가 나올 수 있음.

 

 

 

 

 

다음에 또 봐요