[Python_Search] 백준 1300 : K번째 수

1. 문제

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

1300번: K번째 수

 

 

 

2. 풀이 과정

n이 5이고 검사하는 값을 mid = 6이라고 할 때, 6보다 작거나 같은 값의 수는 아래와 같다.

 

1*1, 1*2, 1*3, 1*4, 1*5

2*1, 2*2, 2*3, 2*4 ,2*5

3*1, 3*2, 3*3, 3*4, 3*5

4*1, 4*2, 4*3, 4*4, 4*5

5*1, 5*2, 5*3, 5*4, 5*5

 

각 행에서 6보다 작은 값의 수는 min(6//(행의 수), n)와 같다. 

n = int(input())
k = int(input())

def search(start, end):
  while start <= end:
    count = 0
    mid = (start+end)//2

    for i in range(1, n+1):
      count += min(mid//i, n)

    if count < k:
      start = mid + 1
    else:
      end = mid - 1
  return start

print(search(1, n*n))