[BOJ 1300번] K번째 수(JAVA)

www.acmicpc.net/problem/1300

1300번: K번째 수

import java.io.*;
import java.util.*;

class Main{
   
   static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
   
   public static void main(String args[]) throws Exception {
	   long N=Long.parseLong(br.readLine());
	   long K=Long.parseLong(br.readLine());
	   
	   long left=1;
	   long right=K;
	   long result=0;
	   
	   while(left<=right) {
//		   System.out.println("*");
		   long cnt=0;
		   long mid=(left+right)/2;
		   for(int i=1;i<=N;i++) {
			   cnt+=Math.min(mid/i, N);
		   }
		   if(cnt<K) {
			   left=mid+1;
		   }
		   else{
			   right=mid-1;
			   result=mid;
		   }
	   }
	   
	   System.out.println(result);
	  
   }
}

아래 글을 참고해서 이번 문제를 풀어보았습니다.

https://devowen.com/265

백준 1300 / 이분 탐색 (Binary Search) / JAVA

위 블로그에서 그림을 통해 잘 설명이 되어 있는데요, k번째 숫자는 mid/i와 N 중에 작은 수를 계속 더한 값이 나온다는 점이 포인트였습니다.

이후 이분 탐색을 이용하여 k번째 숫자를 찾았습니다.