백준_1300 K번째 수 (이분탐색)

이분탐색을 떠올리기도 힘들고 다른 사람의 풀이를 봐도 많이 어려워서 이해하고 받아들이는데 3시간이 걸린 문제

빨간 부분의 증명은 아직도 명쾌히 내리지 못했다.

참고) https://st-lab.tistory.com/281

 

 

추가로 주의할 점은 cnt와 k를 비교하며 탐색범위를 줄일 때

자칫하다가는 cnt == k  일때 정답이겠거니 하고 break를 걸려 m을 출력할 수 있다.

나도 그렇게 생각하고 했다가 계속 틀려서 왜 그런지 생각하느라 애먹었다.

 

cnt==k여도, 탐색 범위의 중앙값 m이 본 문제에서 주어지는 행렬에 존재하지 않는 값일 수가 있기 때문!

 

그렇다면 위의 코드대로 하면 행렬에 존재하는 적절한 값으로 수렴하느냐..?

어차피 작거나 같은 개수를 비교하는 기준인 b[k]는 문제에 존재하는 값이다.

b[k]보다 작은 수는 반드시 cnt가 k보다 작을 것이고, b[k]보다 큰 수의 cnt는 k보다 크거나 같을 것이기 때문에

주어진 코드를 수행하면 점차 문제에서 구하고자 하는 b[k]로 수렴하게 된다.

(굳이 말하자면 cnt가 k보다 크거나 같은 수 중 제일 작은 값으로 수렴)

참고) https://www.acmicpc.net/board/view/119485

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BJ_1300_K번째수 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n, k, s, e, cnt, m, i;

        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());

        s = 1;
        e = k;

        while(s<e+1) {
            m = (s+e)/2;
            cnt = 0;

            for(i=1; i<n+1; i++) {
                cnt += Math.min((m/i), n);
            }

            if(cnt < k) {
                s = m+1;
            } else {
                e = m-1;
            }
        }

        System.out.println(new StringBuilder().append(s));
    }
}

1300번: K번째 수