[PS | 한 번에 맞자!] 백준 1300

0. 문제

K번째 수

1300번: K번째 수

---

1. 문제 생각

일단 "정렬"에 대한 직접적인 언급이 있으나 정렬할 수 없다. N이 최대 10**5인데 NlogN을 수행할 수 없으므로!
그리고 나서는 A에 대한 B를 직접 만들어보았다.
B=[1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, ...]
여기에서 규칙을 찾을 수 있다! 바로 각 숫자가 자신의 "약수의 개수만큼" 나오게 된다.

하지만 이 규칙은 쓰잘때기가 없는데.. 2차원 배열의 index값 N이 무엇으로 나오냐에 따라서 제한 범위가 어디까지인지 저렇게 수열로 나열해서는 알 수가 없다.

그리고... 아이디어를 더 떠올리지 못해 아이디어를 빠르게 참고했다 😥
결정적인 아이디어는 "행으로 나눈 몫"이다.

위에서 볼 수 있는 것처럼 만약 17번째 수를 찾고자 한다면 1행 에서 TARGET보다 작은 수가 16개면 된다.
그러면 1행에서는 몇 개 나오는지, 2행에서는 몇 개 나오는지 .. N행에서는 몇 개 나오는지를 찾아 그 경계선을 찾으면 된다.

이 문제에서는 입력값이 10**5인 것에서 단일 이분탐색의 아이디어를 살짝 눈치채는 것도 괜찮은 방법인 것 같다. 

---

2. 문제 구현

N=int(input())
K=int(input())
start = 1
end = K

while start <= end:
    mid = (start + end) // 2
    num = 0
    for i in range(1,N+1):
        num += min(mid // i, N)
    if num >= K:
        ans = mid ##주의
        end = mid -1
    else:
        start = mid + 1

print(ans)

---

3. 한번에 풀었는가? X
아이디어 생각하지 못함 ㅠㅠ