[BOJ/백준] 1300 K번째 수

N = int(input())
K = int(input())
ST,EN = 1,K
while ST<=EN:
    mid = (ST+EN)//2
    cnt = 0
    for i in range(1,N+1):
        cnt += min(mid//i,N)

    if cnt < K:
        ST = mid + 1
    else:
        EN = mid -1

print(ST)

코드는 간단하지만, 어려웠던 문제였다.

 

자세한 설명은 다른 사람 블로그를 참조하길 바란다.

 

몇몇 케이스를 해보면 알지만 K번째의 수는 절대 K를 넘을 수가 없다.

 

이점을 이용해 1,K로 이분탐색을 한다.

 

각 행을 i라고 하면, 각 행은 i의 배수이다. 

 

즉 N = 5라고 하면 총 5행이 있고, 우리가 찾고자 하는 T = 12 라고 하면

 

1행에서 12보다 작거나 같은 값은 1,2,3,4,5          T//1 = 12

2행에서 12보다 작거나 같은 값은 2,4,6,8,10        T//2 = 6

3행에서 12보다 작거나 같은 값은 3,6,9,12,          T//3 = 4

4행에서 12보다 작거나 같은 값은 4,8,12,            T//4 = 3

5행에서 12보다 작거나 같은 값은 5,10               T//5 = 2

 

위와 같이 보면 우리가 찾고자 하는 값보다 작은 값의 개수는 각 행의 값을 나눈 몫 만큼이다. 그리고 각 행의 열의 개수는 N이므로, N과 비교해서 최소값으로 한다.

 

이분 탐색을 반복하면서 특정 값보다 작거나 같은 값의 개수가 K개가 될때까지 반복해준다. 또한 ST == END가 될때까지 반복해준다. 왜냐하면 K가 되는 값이 여러개가 될수 있으므로, 특정해줘야한다.

K개 에서 그냥 빠져 나올 경우 

N=52, K=276

에서 답이 잘못 나온다.