[백준] BOJ 1300 K번째 수 (Python)

문제링크

이 문제는 접근법을 이해하는것 부터 한참 걸렸다
첫째로, k 보다 작은 수가 몇갠지 찾으면 된다고 한다
(사실 여기서 부터 잘 모르겠다
k=7일때 왜 7 보다 작은 숫자를 찾는건지,,,, 아무리 생각해봐도 모르겠는데 그냥 7보다 작은숫자의 갯수가 7개 보다 적게 나올수는 없어서 그런건가 ...?)

test case 를 N=4, k=7로 잡아봤을때

k 보다 작은 숫자를 찾는다 쳤을때 예시의 상황에서는 이렇다

이거를 이분탐색의 첫 범위로 잡고 시작하면 되고, start <= end일동안 찾으면 된다

start, end = 1, k

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

    for i in range(1,n+1):
        cnt += min(mid//i, n)  
        
    if cnt >= k:
        end = mid - 1
    else:
        start = mid + 1

print(start)

이렇게 잡았을때 k=7 일때 mid는 4이다
그럼 첫번째로는 4이하의 숫자의 갯수가 몇개인지 찾아본다

여기서 아래와 같이 min을 하는 이유는 min 보다 작은 숫자의 갯수가 N개를 넘을수는 없기 때문이다

min(mid//i, n)  

밑에 그림을 보면 5 이하라 한들 N이 4이기때문에 1행에서의 갯수는 min(5//1, 4) = 4개가 된다

다시 본론으로 돌아가서 mid는 4일때, 4보다 작은숫자의 갯수는
총 8개다
내가 찾으려 하는 7개 보다 많다 -> end = mid -1 로 하면 된다

이 상황에서 다음 범위는 이렇게 된다

start, end = 1, 3

mid = 2가 되므로 2 이하의 숫자를 찾으면 된다

이제 총 갯수가 3개로 7보다 작아졌다 -> start = mid+1로 한다

start, end = 3, 3

mid = 3가 되므로 3 이하의 숫자를 찾으면 된다

총 5개로 k개보다 작으므로 start = mid+1로 하면 되는데
이 경우에는 start가 end보다 커지므로 while문이 끝나게 된다

따라서 정답은 4다