[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가 몇 번째에 위치한 숫자인지 알아낼 수 있다.
이진탐색을 어떻게 떠올리느냐,, 증말 어떻게 떠오를까,,,,,,
Author And Source
이 문제에 관하여([BOJ] 1300. K번째 수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ayoung0073/baekjoon-1300-K번째수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)