백준 1300번: K번째 수 [Python]

작성일 | In
골드 I 골드 I

문제

K번째 수

풀이

배열에서 $1$부터 $i$까지 개수의 총합을 $C(i)$라 합시다.

우리는 $C(i) \ge k$인 $i$의 최솟값을 찾으면 됩니다.

$r$행에서 $i$보다 작은 수의 개수는 $i$ 이하의 $r$의 배수와 같고, 이는 $\lfloor i / r \rfloor$로 계산할 수 있습니다.

따라서 $C(i)$를 $O(N)$에 계산할 수 있고, 이분 탐색을 이용하면 $O(N\log N^2) = O(N\log N)$에 해결할 수 있습니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def main():
    N = int(input())
    k = int(input())

    def get_le_count(n: int) -> int:
        ret = 0

        for i in range(1, N + 1):
            ret += min(n // i, N)

        return ret

    lo = 0
    hi = N * N
    while lo < hi:
        mid = (lo + hi) // 2

        if get_le_count(mid) >= k:
            hi = mid
        else:
            lo = mid + 1

    print(lo)


main()

백준 1300번: K번째 수 [Python]