[BAEKJOON] 1300. K번째 수

 

문제링크

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

1300번: K번째 수

 

이중탐색

1 2 3

2 4 6

3 6 9

 

low = 1, high = 7 이라면

mid = 4 가 되고

배열에서 4보다 작은 수는 cnt = 6(3 + 2 + 1)이 된다.

 

이중탐색이 끝날 때까지 cnt를 최신화한다.

package acmicpc.Gold3;

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

public class K번째_수 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		long k = Integer.parseInt(br.readLine());
		
		long left = 1;
		long right = k;
		long cnt = 0;
		long ans = 0;
		
		while(left <= right) {
			long mid = (left + right) / 2;
			cnt = 0;
			for(int i = 1 ; i <= n ; i++) {
				cnt += Math.min(mid / i, n);
			}
			
			if(cnt >= k) {
				ans = mid;
				right = mid - 1;
			} else {
				left = mid + 1;
			}
			
		}
		System.out.println(ans);
	}
}