📝 문제 정보#
🧐 관찰 및 접근#
- 나이브하게 계산한다면, 정수가 $10^{10}$개 있으니 아무것도 안된다. 심지어 저장도 불가능하다.
- 어떤 수 $X$가 주어질 때, $X$보다 작거나 같은 수가 몇개인지는 $O(N)$에 셀 수 있다.
- 그리고 $X$보다 작거나 같은 수가 $K$개 이상인 수중 가장 작은 $X$가 정답이다.
- 따라서 파라메트릭 서치를 이용해 $O(N\log{10^9})$정도에 계산하자.
💻 풀이#
- 코드 (python):
N = int(input())
K = int(input())
def count(X): # 배열에서 X 이하 수의 개수
result = 0
for i in range(1, N+1):
result += min(N, X // i)
return result
ok = N*N
ng = 0 # 답의 범위는 [1, N*N]이므로
while ok - ng > 1:
mid = (ok + ng) // 2
if count(mid) >= K:
ok = mid
else:
ng = mid
print(ok)