문제 링크

<aside> 💡 이분 탐색/매개 변수 탐색

</aside>

Memory 114488KB Time 164ms Code Length 332B

import sys
input = sys.stdin.readline

def calc(mid):
    cnt = 0
    for i in range(1, N+1):
        cnt += min(mid//i, N)
    return cnt

N = int(input())
k = int(input())

left, right = 1, k
while left < right:
    mid = (left + right) // 2
    if calc(mid) >= k:
        right = mid
    else:
        left = mid + 1

print(left)

이 코드는 이진 탐색을 이용해 K번째로 작은 수를 찾는 프로그램이다.

먼저 'sys' 모듈을 불러와서 입력을 빠르게 받을 수 있게 준비한다. 그리고 'calc'라는 함수를 정의한다. 이 함수는 주어진 중간값 'mid'를 이용해 1부터 N까지의 수를 각각 'mid'로 나눈 몫을 더하거나, N을 더하는 방식으로 'cnt'를 계산한다. 이렇게 계산된 'cnt'는 'mid'보다 작거나 같은 수의 개수를 의미한다.

그 다음으로 사용자로부터 두 개의 정수 N과 k를 입력받는다. 그리고 이진 탐색을 위한 초기 범위를 1부터 k까지로 설정한다.

이진 탐색을 시작하면서 범위의 중간값 'mid'를 구하고, 'calc(mid)'의 결과가 k 이상인지 확인한다. 만약 k 이상이라면, 범위의 오른쪽 끝을 'mid'로 변경한다. 그렇지 않다면, 범위의 왼쪽 끝을 'mid + 1'로 변경한다.

이진 탐색이 끝나면, 최종적으로 남은 범위의 왼쪽 끝값이 K번째로 작은 수가 된다. 이 값을 출력한다.