def cal(x):
n = min(int(x**0.5),N)
cnt = 0; same = 0
for i in range(1,n+1):
m = min(x//i,N)
cnt += m
same += int(x==m*i)*2
return cnt*2-n**2+1, same-int(n**2==x)
def find(x,c):
k,s = cal(x)
if k<=K:
return find(x+2**c,c-1)
if k-s>K:
return find(x-2**c,c-1)
return x
N = int(input()); K = int(input())
print(find(1<<34,33))
이분탐색으로 해결하였다.
풀이를 설명하면,
1. cal 함수는 N*N 배열에서 x보다 작거나 같은 숫자의 개수가 몇 개 존재하는지를 계산하는 함수이다. 이때 작거나 같은 숫자들의 개수와 x와 같은 숫자의 개수를 출력한다.
2. find 함수는 이분탐색을 해주는 함수이다. x일 때 (x보다 작은 숫자들의 개수) < K <= (x보다 작거나 같은 숫자들의 개수) 가 성립하면 x가 K번째 숫자임을 의미하므로 이를 출력한다.
3. 2^34에서 시작해서 이분탐색을 통해 K번째 수를 구해준다.
오늘의 교훈) 이분탐색을 적절하게 활용하자