Intuition

일단 1차원 배열을 직접 만들려면 O(N^2)라서 불가능합니다. 그렇다면 O(NlogN)의 풀이가 있을까 고민하게 되는데, 파라메트릭 서치를 이용하여 k번째 수가 될 수 있는 숫자를 임의로 대입해보면서 K번째 숫자가 될 수 있는지 로직을 구성하면 되겠다 생각했습니다. 이렇게 하니 O(N logNN)정도로 계산되므로 최악의 경우 약 10^6 정도의 연산을 할 것이니 적절한 풀이라 보았습니다.

Algorithm

이분탐색 로직을 이용하여 1부터 N*N 사이의 숫자를 하나 지정합니다.
해당 숫자의 앞에 몇 개의 숫자가 존재할 수 있을지 계산합니다.
계산된 값을 lower_bound 이분탐색 로직으로 반복하며 K번째 숫자를 찾아냅니다.

이 문제의 포인트는 lower_bound입니다. 중복된 숫자가 존재하는 수열 상에서 K번째 숫자가 무엇인지 찾는 로직이므로, 해당 숫자가 최초로 등장하는 인덱스를 찾아내는 lower_bound 로직으로 찾아내야 합니다.

import sys
input = sys.stdin.readline

N = int(input())
K = int(input()) - 1

def cal(t):
    res = 0
    for i in range(1, N+1):
        if t // i <= N:
            res += t // i
        else :
            res += N
    return res

def lower_bound():
    left = 1
    right = 10**18
    while left < right:
        mid = (left + right) // 2
        if cal(mid) > K:
            right = mid
        else:
            left = mid + 1
    return left

print(lower_bound())

Complexity Analysis

• time complex : O(N * log N*N)
• space complex : O(1)