boj.kr/1300 K번째 수 (gold2) 파이썬 풀이

1. lo를 0, hi를 k으로 초기화한다.

2. lo가 hi보다 작거나 같으면 아래 3-6을 반복한다.

3. mid 를 (lo+hi)//2 으로 초기화한다.

4. 1부터 N까지 반복하면서 mid//i와 N중 작은 값을 cnt에 더하기함으로서 mid보다 작거나 같은 수의 개수를 구한다.

5. mid보다 작거나 같은 수의 개수 cnt가 k와 같거나 더 크면, hi를 mid-1으로 갱신하고 ans변수에 mid를 저장한다.

6. cnt가 k보다 작으면, lo를 mid+1으로 갱신한다.

7. ans를 출력한다.

 

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

lo = 0
hi = k

while lo <= hi:
    mid = (lo + hi) // 2
    cnt =0
    for i in range(1, N+1):
        cnt += min(mid//i, N)

    if cnt >= k:
        hi = mid-1
        ans = mid
    else:
        lo = mid+1

print(ans)

 

모든 수를 검사할 필요 없이 lo를 0으로 , hi를 k로 초기화하고 mid보다 작거나 같은 수들의 개수가 k에 가장 가까울 때까지 이분탐색한다. 왜냐하면 k보다 작거나 같은 수들의 개수가 항상 k개 보다 많기 때문이다.

 

참고출처

"#396 백준 파이썬 [1300] K번째 수 - 이분탐색", claude-u.tistory.com, 2020년 2월 11일 수정, 2023년 5월 28일 접속, https://claude-u.tistory.com/449