백준 1300번 k번째 수

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

n = int(input())
k = int(input())
left = 1
right = n*n
ans = -1
while left <= right:            # 이분 탐색으로 k 번째 숫자를 구한다
    mid = (left + right) // 2
    cnt = 0
    for i in range(1, n+1):         # 이분 탐색으로 구한 숫자를 row 인덱스 (1부터 시작) 로 나누면, 해당 숫자보다 작거나 같은 숫자 개수를 구할 수 있다.
        cnt += min(n, mid // i)
    if cnt >= k:                    # 작거나 같은 수가 k 보다 많은 경우
        ans = mid                       # 정답이 될 수 있다. (같은 크기가 여러개인 경우도 존재)
        right = mid - 1
    else:                           # 작거나 같은 수가 k 보다 작은 경우
        left = mid + 1

print(ans)

• 이분 탐색으로 k 번째에 위치한 숫자를 구한다.
  
  
• 이분 탐색으로 구한 숫자 mid 를 row 인덱스 (1부터 시작) 로 나누면, 해당 숫자보다 작거나 같은 숫자 개수를 알 수 있다.
  • 작거나 같은 숫자개수가 k-1 개라면, 해당 숫자는 k 번째 수이다.
    
  • 이분 탐색으로 구한 mid 가 8 이라고 가정할 때
  • 첫 번째 행은 8 // 1 = 8 인데, 한 행의 길이 n 을 넘을 순 없으므로, 5개가 작거나 같은 수가 된다.
  • 두 번째 행은 8 // 2 = 4 이므로, 4개가 작거나 같은 수가 된다.
    
    
• 작거나 같은 숫자가 k 보다 많으면, mid 가 정답이 될 수 있으므로 체크하고, 숫자 (mid) 값을 줄인다.
• 작거나 같은 숫자가 k 보다 작으면, 숫자 (mid) 값을 키운다.

출처: 알고리즘 중급 1/3 강의
https://code.plus/course/43