1300번 K번째 수

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

---

아이디어

아이디어를 생각하는 게 어려웠던 문제이다.

우선 B[k]에서 k는 B[k]의 원소 값보다 작거나 같은 원소의 개수이다.
B[k]=x인데 우리는 x를 찾아야한다. 그럼 x보다 작거나 같은 원소의 개수가 k랑 일치하면 된다.

우리는 이 x를 이분탐색으로 찾아야한다.
x보다 작은 원소들의 개수를 어떻게 찾을 수 있을까?

행렬의 인덱스가 1부터 시작한다고 했으므로 각 행은 1단, 2단, 3단 ...으로 볼 수 있다.
x가 20이라고 했을 때
1단에서 20보다 작거나 같은 수의 개수는? 20 // 1 = 20
2단에서 20보다 작거나 같은 수의 개수는? 20 // 2 = 10
3단에서 20보다 작거나 같은 수의 개수는? 20 // 3 = 6
...
3단까지 했을 때 20보다 작거나 같은 수의 개수는 20 + 10 + 6 = 36(개)이다.

만약 N=4, K=20일 때
행렬은
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16
이때 20보다 작거나 같은 수의 개수는 아까처럼 20 // 1, 20 // 2 ... 이런 식으로 구하면 안된다. 행렬 크기가 4X4이므로 행에서 K보다 작거나 같은 수는 최대 4개가 나올 수 있다.

while low <= high:
    mid = (low+high)//2
    cnt = 0
    for i in range(1, n+1):
        cnt += min(n, mid // i)

그래서 이렇게 n, mid//i 중 작은 값을 cnt에 더해줘야 한다.
이때 cnt는 mid보다 작거나 같은 수가 몇 개 있는지 세는 변수이다.

참고한 블로그

---

코드

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

low = 1
high = k
answer = 0
while low <= high:
    mid = (low+high)//2
    cnt = 0
    for i in range(1, n+1):
        cnt += min(n, mid // i)

    if cnt < k:
        low = mid + 1
    else:
        high = mid - 1
        answer = mid
print(answer)