1300 K번째 수

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

1300번: K번째 수

 

알고리즘 분류

1. 이분탐색

 

아이디어

1. N이 10의 5승이기 때문에 O(n^2)시간복잡도로 풀면 시간이 오래 걸릴 것임

2. 이분탐색으로 O(logn) 시간복잡도로 푸는 것으로 접근

3. 탐색 범위를 목표한 수로 잡고 탐색한 수의 이하의 정수들이 행렬에 몇개가 있는지 생각해서 탐색

4. 17 ~ 18번째 라인이 생각하기 어려운데 행마다 for문을 돌면서 행렬의 값이 i * j 이므로 최대 몇개가 있을지 고려함

-> min을 쓴 이유는 목표값 나누기 i 의 값이 현재의 열 수보다 크면 최대 열의 수만큼만 존재함으로 이를 고려

if __name__ == "__main__":
    n = int(input())
    k = int(input())

    low = 1
    high = n * n

    res = -1

    while True:
        if low > high:
            break

        mid = (low + high) // 2
        cnt = 0

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

        if cnt >= k:
            res = mid
            high = mid - 1
        else:
            low = mid + 1
    print(res)