[파이썬] [이진탐색] 백준 1300 K번째 수

문제

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

1300번: K번째 수

코드

n=int(input())
k=int(input())

start=1
end=int(1e9)
answer=0

while start<=end:
    mid=(start+end)//2

    temp=0
    for i in range(1,n+1):
        temp+=min(mid//i,n)

    if temp<k:
        start=mid+1
    else:
        end=mid-1
        answer=mid

print(answer)

생각 정리

A보다 작은 숫자가 몇개인지 찾아내면 A가 몇 번째 숫자인지 알 수 있다.

예를 들어 10 * 10에서 20보다 작거나 같은 수를 생각해보자.
1*1~1*10
2*1~2*10
3*1~3*6
.
.
.
10*1~10*2

위 수가 존재할텐데, 이는 반대로 생각해보면 20을 행으로 나눈 몫이다.

20//1: 10개 --> 단 열의 숫자를 초과할 수 없다.
20//2: 10개
20//3: 6개
.
.
.
20//10: 2개