https://www.acmicpc.net/problem/1300
def binary_search(start, end):
global res
if start > end:
return
mid = (end + start) // 2
cnt = 0
for i in range(1, n + 1):
cnt += min(n, mid // i)
if cnt < k:
binary_search(mid + 1, end)
else:
res = mid
binary_search(start, mid - 1)
n = int(input())
k = int(input())
res = 0
binary_search(1, min(10 ** 9, n ** 2))
print(res)또 혼자 문제를 못 풀고 답을 참고했다. 이분 탐색을 어떻게 적용해야하는지 생각해내지 못했다. A배열을 만들고, 정렬한 후에 k번 째 수를 찾으면 안되겠다고 당연히 생각했었는데 다른 방법이 잘 생각이 안난다.
핵심은 B[k]보다 작은 수들을 알아야 하는 것이 아니라, 그저 몇 개인지 숫자만 세면 된다는 것이다. 규칙적인 A배열에서 어떤 한 수보다 작은 수들의 개수를 세는 것은 쉬운 일이기 때문이다. B[k]가 될 수 있는 수를 가정하여 작은 수들의 개수를 세고, 판단하며 이분 탐색으로 B[k]를 찾으면 된다.
한 가지 함정은 cnt와 k의 비교인데, cnt가 작다면 가정한 B[k]가 작기 때문임이 명백하다. 하지만 정답인 B[k]를 찾은 경우에 같은 숫자가 겹치는 경우 cnt가 k보다 클 수도 있다.
handsome