문제

1300번: k번째 수

풀이

문제의 n이 최대 100000 이므로 n 제곱은 100억이 된다. 따라서 b 배열을 전부 구한 후 정렬하여 문제를 해결할 수 없고, 이분탐색으로 원하는 값을 찾아야 한다.
하지만 이분탐색으로 어떻게 구현해야 할지 생각하기 너무 어려웠다.

우선 구해야 할 수는 배열 B 에서 k 번째 수이다. 이 수를 x 라고 했을 때,
우리가 알고 있는 수는 k, 구해야 하는 수는 x다. x를 매개변수로 하는 함수값을 k와 비교하여 그 결과를 토대로 x를 조정하며 k와 이분탐색 조건에 부합하는 값 x를 찾는 것이 목표다.

배열B에서 k번째 수는 x이다. 라는 말을
x보다 작거나 같은 수는 배열B에서 k개 있다. 고 바꿔말할 수 있다.
x를 이용하여 k와 비교할 값을 만들 수 있게 되었다. 이를 f(x)라고 하면

x	1	2	3	4	5	6	7	8	9
f(x)	1	3	5	6	6	8	8	8	9

x의 값을 변경하며 k와 f(x)의 값을 비교하고 일치하는 값의 x를 출력하면 문제를 해결할 수 있다.
하지만 f(x)는 k와 일대일 대응하지 않는다.
예를 들어 k=7 인경우, x는 5 혹은 6이다. 실제로 대입해보면 f(5) = 6, f(6) = 8로
5보다 작거나 같은 값은 6개, 6보다 작거나 같은 값은 8개다. x가 5라면 최대 6번째로 큰 수가 된다는 뜻이다. 6은 8번째로 큰 수가 된다는 뜻이 되므로 k=7인 경우 lower bound 로 7 이상인 값 8이 처음 나온 x=6일 때를 선택해야 한다.

코드

#include <iostream>
#include <vector>**텍스트**

using namespace std;

int64_t n;
int64_t k;

int64_t min(int64_t a, int64_t b) { return a > b ? b : a; }

int64_t calRank(int64_t num){ // 작거나 같은 값의 개수
    int64_t ret = 0;
    for (int i=1; i<=n; i++){
        ret += min(num / i, n);
    }
    return ret;
}

int main() {
    cin >> n;
    cin >> k;
    
    int64_t lo = 0;
    int64_t hi = n*n;
    while (lo <= hi) {
        int64_t mid = (lo + hi) / 2;

        if ( calRank(mid) < k)
        // if (k <= calRank(mid) )
            lo = mid + 1;

        else 
            hi = mid - 1;

    }
    cout << lo << endl;
    return 0;
}