백준 1300 - k번째 수

문제 링크

파라메트릭 서치를 사용하는 흥미로운 문제다.

모든 수는 \(i \times j\) 형태이다. 어차피 모든 원소는 1 ~ \(n^2\) 안에 들어온다. 그러니 탐색 범위는 정해져있고, 아무거나 찍은 x가 k번째 수가 되려면, x 밑에 \(i \times j\) 형태로 나오는 수가 몇개 있는지(=c) 세면 된다.

만약 \(c < k\) 라면, x를 더 크게 잡아야한다.
\(c \geq k\) 라면, 어떻게 하지? 같은수가 중복으로 나올 수 있기 때문에 무조건 \(x\)를 낮추면 안된다.
\(x-1\)일때 조건이 \(c < k\) 면 통과다. 세는 김에 같이 세자.

\(i \times j < x\) 를 만족하는 갯수를 셀 때 굳이 이중 for loop으로 할 필요가 없다. 시간만 오래걸린다. \(j = x \div i\) 임을 이용하자. 단, \(j\) 가 n을 못넘어간다는것만 주의하면 된다.

실제 구현에서는 항상 overflow를 주의하자. 자료형을 넉넉하게 잡으면 된다.

#include <stdio.h>
#define min(a,b) ((a)>(b)?(b):(a))

long n, k;

int solve() {
    long st = 1, en = n*n, m;
    long c1, c2, i;

    while (st < en) {
        m = (st+en+1)/2;

        c1 = c2 = 0;
        for (i=1; i<=n; i++) {
            c1 += min(m / i, n);
            c2 += min((m-1)/i, n);
        }

        if (c1 < k) {
            st = m;
        } else if (c2 < k) {
            return m;
        } else {
            en = m - 1;
        }
    }

    return st;
}

int main() {
    scanf("%ld %ld", &n, &k);

    printf("%d\n", solve());

    return 0;
}