(파이썬) 백준 1300번 "K번째 수"

---

# 답

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

lo = 1
hi = N * N
mi = (lo + hi) // 2

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

    if k <= cnt:
        hi = mi - 1
    else:
        lo = mi + 1
    mi = (lo + hi) // 2

print(mi + 1)

 

 

 

 

---

# 풀이 과정

 

이분 탐색으로 푸는 문제입니다.

우리가 구해야 되는 답은 'k번째로 큰 수'입니다. 이 수는 적어도 1이상이며, 아무리 커도 N * N 이하입니다. 즉 1과 N * N 사이에 있는 수 중에서 정답이 있다는 뜻입니다. 1 ~ N * N 사이의 수를 절반씩 줄여나가며 탐색하다보면 정답에 도달할 수 있을 것입니다.

lo = 1
hi = N * N
mi = (lo + hi) // 2

 

lo와 hi 사이에 있는 숫자 mi가 k번째 숫자일까요?

mi가 몇 번째 숫자인지 알려면, mi 이하의 숫자들이 몇 개 있는지를 알아야합니다.

N * N 배열의 1행부터 차례대로 탐색하며 mi보다 작은 숫자의 개수(cnt)를 세봅시다.

i번째 행에서 mi보다 작은 숫자의 개수는 mi를 i로 나눈 몫과 같습니다. 단, 한 행에는 N개의 숫자만 있으므로 한 행에서 mi보다 작은 숫자의 개수는 N을 초과할 수 없습니다.

cnt = 0
for i in range(1, min(mi, N) + 1):
    cnt += min(N, mi // i)

 

이렇게 해서 mi보다 작거나 같은 숫자의 개수 cnt를 구했습니다. 숫자 mi는 cnt번째로 큰 숫자 부근의 수입니다.

우리가 구해야 되는 건 k번째로 큰 숫자가 무엇인지였죠?

cnt가 k보다 크거나 같다면(숫자 mi가 정답보다 크거나 같다면), 탐색범위를 낮춰야됩니다.

반대로, cnt가 k보다 작다면 (숫자 mi가 정답보다 작다면), 탐색범위를 높여야됩니다.

탐색범위를 조정한 후, 다시 위 과정들을 반복해주면 답을 구할 수 있습니다.

if k <= cnt:
    hi = mi - 1
else:
    lo = mi + 1
mi = (lo + hi) // 2