[백준] 1300 K번째 수

문제보기

이분탐색… 으로 풀 수 있는지 없는지를 판단할 수 있는 능력이 시급하다. ㅠㅠ
해결법의 컨셉은 간단하다. 어떤 숫자를 잡는다 -> 그 숫자이하의 원소의 갯수가 K보다 큰지 작은지를 판단한다 -> 작다면 그 숫자를 키워준다 / 크다면 그 숫자를 줄여준다 -> K와 같아질 때까지 반복한다.

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

class Main{
	
	static int ip(String s){ return Integer.parseInt(s); };

// x번째 이하의 원소의 갯수를 반환하는 함수 
	static int getCnt(int x, int n) {
		int cnt = 0;
	// i : 각 열(row)
	// 각 열의 원소의 갯수는 최대 n개이며, x/i개와 n개 중 더 작은쪽이 해당 열에서 x보다 작은 원소의 갯수가 된다.
		for(int i = 1 ; i <= n ; i++) {
			cnt += Math.min(x/i, n);
		}
		return cnt;
		
	}
     public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	int n = ip(br.readLine());
    	int k = ip(br.readLine());
    	
    	int l = 1; // 최소 숫자는 1
    	int r = (int) Math.min((long) n*n, 1000000000); // 최대 숫자는 이거
    	int mid; // 중간값이 될 녀석
    	int ans = 0; // k번째 숫자가 담길 변수 
    	
    	while(l <= r) {
    		mid = (l+r)/2; // 중간값 잡고
    		int cnt = getCnt(mid, n); // 갯수 얻기
    		
    		if(cnt >= k) { // 만약 k개보다 많았다면
    			r = mid-1; // 범위를 좁힌다
    			ans = mid; 
    		}else { // k개보다 적다면 
    			l = mid+1; // 범위를 넓힌다
    		}
    	}
    	System.out.println(ans);
     }
}