[백준 1300번] K번째 수 (Python3)

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번째 수를 구해준다.

 

 

오늘의 교훈) 이분탐색을 적절하게 활용하자