[백준] K번째 수

https://www.acmicpc.net/problem/1300

1300번: K번째 수

 

N = 5 로 예를 들면,

N * N 배열은 아래와 같다. 

[1, 2, 3, 4, 5]

[2, 4, 6, 8, 10]

[3, 6, 9, 12, 15]

[4, 8, 12, 16, 20]

[5, 10, 15, 20, 25]

 

이분 탐색으로 나올 수 있는 수 중 최솟값인 1과 최댓값인 5*5(=25)를 시작으로 한 중간값(=mid)이 조건에 맞는지를 확인한다. 배열 안에 중복된 값이 여러 개 있으므로 mid 보다 같거나 작은 것의 개수가 k 보다 크거나 같은 것 중 가장 가장 작은 mid 가 정답이 된다. 

 

작은 것의 개수는 mid 를 i (i = 1, 2, ..., N) 으로 나누었을 때의 몫들의 합이라고 할 수 있다. 단, 하나의 행에서 나올 수 있는 개수의 최댓값은 N 이기 때문에 N 보다 큰 값은 나올 수 없다.

 

import sys

N = int(sys.stdin.readline())
k = int(sys.stdin.readline())

start = 1
end = N * N
answer = 0

while start <= end:
    mid = (start + end) // 2
    count = 0 
    
    for i in range(N):
        count += min(mid // (i + 1), N)
        
        if count >= k:
            answer = mid
            end = mid - 1
            break
    
    else:
        start = mid + 1
        
print(answer)