Node.js) 백준 1300번 : K번째 수

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

1300번: K번째 수

이분탐색으로 풀라고 안 알려줬으면 절대 못 풀었을듯

const fs = require('fs');
const [N, K] = fs.readFileSync("./dev/stdin").toString().trim().split("\n").map(v => +v);

let min = 1;
let max = K;
let answer = N * N;

while (min <= max) {
  let mid = Math.floor((min + max) / 2);
  let cnt = 0;
  for (let i = 1; i <= N; i++) {
    cnt += Math.min(Math.floor(mid / i), N)
  }
  if (cnt < K) {
    min = mid + 1;
  } else {
    if (answer > mid) answer = mid;
    max = mid - 1;
  }
}
console.log(answer)

 

풀 때 썼던 메모장

1 2 3           
2 4 6
3 6 9

i  1 2 3 4 5 6 7 8 9
n 1 2 2 3 3 4 6 6 9

7번쨰 있는 수를 찾는다. 

그러니까 7번째가 어떤 수 x면.  원래 배열에 x보다 작거나 같은 게 7개 있어야함?,,,

그 수는 1부터 9 사이? 

min = 1 max = 9  mid = 5
5보다 작거나 같은게  123 24 3 6개   이 6이 7보다 작으니까,  다시 이분탐색


min = 6 max = 9  mid = 7 
7보다 작거나 같은게 1 2 3 2 4 6 3 6  8개. 7보다 크네? 

min=6  max=6   mid=6

1 2 3 2 4 6 3 6 8개  7보다 크다?  
min= 6 max = 5
break; 하고. answer = 6  

그러니까. mid보다 작거나 같은거 다 찾아서 카운트하고 max를 mid-1.
그게 index보다 크다? 그러면 min 을 mid+1로