<Algorithm> 181. K번째수(BJO)

1. 1300번 K번째수(BJO)

   사용 알고리즘 :  이분탐색

• 이분탐색으로 푸는 것을 알고 봤는데도 전혀 이해가 안됬던 문제, 정답 코드를 봤는데도 이해하기 쉽지 않았다.

• 의문점이 들었던 부분은 1. n*n이아닌 k의 범위로 했을때도 정답이 출력됨, 2. 왜 조건(>=)을 만족하는 최솟값이 정답인지?

• 1번은 중복없이 1 2 3~ 나열할때 K번째수를 구하면 딱 번호가 자기자신이 되므로 중복이 발생하면 더더욱 K번째 이하일 수 밖에 없다.

• 2번은 n의 범위에 없는 수가 있어서 였다. 3*3에서 5는 나오지 않지만 이분탐색하면 5를 탐색한다. 

• 이때 5는 6의 count를 가지게 되고 4도 6의 count를 가지게 된다. 이때 5는 범위에 속하지 않기 때문에 정답이 될 수 없다. 

• 또한 3의 경우 5의 count를 가지지만 4번도 될 수 있기 때문에 조건을 만족하는 수중에 최솟값이 정답이 되는 것이다.

내 코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

import java.util.Scanner;   public class Main {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         int k = sc.nextInt();         int start = 1,end=k+1;         int ans = 0;         /***************************          * 이분탐색을 이용해 K번째수를 구한다.          * 이때 중첩되는 갯수가 발생하기 때문에          * i*j의 배수를 이용하여 갯수를 판단한          * 이분탐색으로 원하는 원소를 찾는다.          ***************************/         while (start<end) {             // start < end 이므로 end까지 돌려면 +1을 해야한다.             int mid = (start+end)/2;             int count = 0;             for(int i = 1; i <= n; i++) {                  count+=Math.min(mid/i,n);// n보다 큰수는 있을수 없다.             }             if(count >= k) {                 ans = mid;                 end = mid;             }else {                 start = mid+1;             }         }         System.out.println(ans);     } }   Colored by Color Scripter

cs