1300 k번째 수

어떻게 이분탐색으로 해야할 지 감이 안왔던 문제

근데 되돌아보니 수업 때 11122233345 이런식으로 예시를 보여주셨던게 생각났다... 아..!

 

먼저 완전탐색으로 다 보면 n*n = 10^5라서 볼 수 없다

 

최적화를 해야되는데 ..

1에서 n*n까지 이분탐색을 한다? -> 이분탐색으로 뭘 어떻게 할건데? 만 생각났었다.

 

이분탐색으로 값의 범위를 줄여가면서 이분탐색으로 찾은 중간값(mid) 이하인 숫자가 몇 개 있는지 찾으면 된다.

 

 

이 때 중간값(숫자)보다 m이 더 크면 중간값은 답이 될 수 없고 무조건 중간값 + 1이어야 한다.

중간값(숫자)보다 m이 작으면 답은 중간값이 될 수도 있고 그 밑에 값이 될 수도 있고 .. 그러하다. 이때 mid - 1을 해준다.

 

아 어렵다.