[백준 1300번] K번째 수 -python

문제 링크

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

1300번: K번째 수

 

풀이 

이분 탐색 문제 

- 이분 탐색으로 K보다 작은 자연수의 곱(i*j)가 몇 개인지 알아낸다.

- K보다 작은 숫자가 몇 개인지 찾아내면 K가 몇번째 숫자 인지 알 수 있다. 

이 때, 임의 수 a보다 작거나 같은 수의 개수는 

( a //  행번호 ) 가 해당 행에서 구하고자 하는 수 

단, ( a// 행번호) 가 N보다 클 때는 N

N = int(input())

k = int(input())

start = 1
end = k
answer = 0 

while start <= end :
  mid = (start + end)//2

  tmp = 0 
  
  # K보다 작은 자연수 개수 구하기 
  for i in range(1, N+1):
    tmp += min(mid // i, N)
  
  if tmp >= k:
    answer = mid 
    end = mid -1 
  
  else:
    start = mid + 1 

print(answer)