[BOJ] 1300. K번째 수

문제 링크

n = int(input())
k = int(input())
start, end = 1, k

while start <= end:
    mid = (start + end) // 2
    
    count = 0
    for i in range(1, n + 1):
      # 이진 탐색으로 어떤 수(mid)보다 작은 자연수의 곱(i의 배수)이 몇 개(count)인지 알아낸다.
      count += min(mid // i, n)
      
	# 이진 탐색
    if count >= k: # count가 k 이상이면, 인덱스가 k보다 큰 위치에 있다.
        answer = mid
        end = mid - 1
    else: # count보다 더 큰 위치에서 탐색해야한다.
        start = mid + 1

print(answer)

이진탐색으로 푸는 문제
해당 숫자(mid)보다 작거나 같은 숫자들을 전부 찾아 mid가 몇 번째에 위치한 숫자인지 알아낼 수 있다.

이진탐색을 어떻게 떠올리느냐,, 증말 어떻게 떠오를까,,,,,,