문제

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

코드

n=int(input())
k=int(input())

def counter(x):
    small=0
    big=0
    for i in range(1,n+1):
        # i 번째 행에서 x 보다 작은 수
        small+=min(n,(x-1)//i)
        # i 번째 행에서 x 보다 큰수
        big+=n-min(n,x//i)

    return (small,big)

number=-1
left=1
right=min(n*n,int(1e9))
total=n*n

while left <= right:
    mid=(left+right)//2

    small,big=counter(mid)

    if small > k-1:
        right=mid-1
    if big > total-k:
        left=mid+1


    if small<=k-1 and big <=total-k:
        number = mid
        break

print(number)

설명

처음엔 b=[]에 i*j를 모두 넣어서 sort 해서 할려고 했다. 근데 골드인만큼 절대그건 불가능했다. ㅋㅋ

이분탐색인 것을 알고

이런식으로 풀었다.
x라는 k번째 수는 k-1개의 작은개수와 n*n-k의 큰수를 가지고 있다.
이를 기준으로하여 최적의 수를 이분탐색으로 찾아나서는 것이 핵심이다.

두번째 위기 봉착은
작은것과 큰수의 개수를 세는 과정이다. 처음엔 이중 for문으로 탐색했는데 여기서 시간초과가 발생했다. 10^9개의 자료를 돌릴땐 O(n^2)이 되다보니깐 시간오버가 되는 것같다.

이를 해결하고자
https://www.inflearn.com/course/%EB%96%A0%EB%A8%B9%EB%8A%94-%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8
를 참고했다.