악곱 == 악성곱슬

이분 탐색

---

이 문제는 NxN 정방행렬이 있을때 해당 값의 원소를 오름차순으로 정렬 했을 때 k 번째 수를 구하는 문제이다. 다만 행렬의 값은 i x j 로 고정되어있다.

입력값의 범위는 N = 10만으로 수가 매우 크다. 따라서 직접 행렬을 생성하고 정렬해볼수는 없다. 입력값의 크기와 k의 범위를 보면 O(M) (M = NxN)으로도 해결할 수가 없다. 따라서 O(logM) 이하로 해결해야 한다. 따라서 이분 탐색을 생각해볼 수 있다.

이분 탐색을 어디에 적용해야 하는가?

이 문제는 i x j 로 행렬 값이 고정되어있다는 성질을 이용해야 한다. i 가 1이라면 해당 행은 1의 배수, 2라면 2의 배수 3이라면 3의 배수… 이렇게 진행된다. 따라서 min(10^9, N^2)을 각 행으로 나누어서 몫의 개수를 구하면 k보다 작은 값의 개수를 셀 수 있다. 이를 반복하다보면 O(NlogN)으로 내가 원하는 값을 전부 탐색하지 않고 찾아갈 수 있다. 코드는 다음과 같다.

구현

---

def count(n, d):
    cnt, zero_r = 0, 0
    for i in range(1, n + 1):
        cnt += min(n, (d // i))
        if (d % i) == 0 and (d // i) <= n:
            zero_r += 1
    return cnt, zero_r

def solution(n, k):
    answer = 0
    start, end = 1, min(INF, n**2)
    while start <= end:
        mid = (start + end) // 2
        cnt, zero_r = count(n, mid)
        if zero_r and cnt - zero_r < k <= cnt:
            answer = mid
            break
        if cnt < k:
            start = mid + 1
        else:
            end = mid - 1
    return answer

if __name__ == "__main__":
    N = int(input())
    K = int(input())
    INF = int(1e9)
    print(solution(N, K))