[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)

코드는 간단하지만 어려운 문제였다.

 

기본적인 원리는 이러하다. 

N*N 행렬이 있고, 그 안의 값은 해당 row index와 col index의 곱이 된다.

 

그렇다면 해당 줄에서 주어진 값 X보다 작은 값은 row_index로 나눈 몫일것이다.

 

만약 N = 5 이고 주어진 X가 12라면,

 

1행 : 1,2,3,4,5

2행 : 2,4,6,8,10

3행 : 3,6,9,12,15

4행 : 4,8,12,16,20

5행 : 5,10,15,20,25

 

이다. 이럴때 12보다 작은 값들은 1행에 5개, 2행에 5개 3행에 4개 4행에 3개 5행에 2개이다.

 

즉 12를 row의 index로 나눈 몫과 동일하다.

 

이를 통해, cnt가 K개가 될수 있는 X를 찾아주면 된다.

 

그리고 초기 값의 END가 K인 이유는 K번째 수는 K보다 작거나 같기 때문이다.