1300번_K번째 수_BOJ

문제 링크

1300번 K번째 수 : https://www.acmicpc.net/problem/1300

문제 설명 및 해결 아이디어

이 문제를 그냥 구현하게 되면 시간초과가 난다. Parametric Search로 해결할 수 있다.

mid값은 1부터 K까지의 범위안에서 움직여주자. 

이 문제를 풀기 위해서는 다음의 내용을 알아야 한다.

즉, 특정한 mid값은 mid이하의 수의 개수가 주어진 K개 이상이면서 가장 작은 수가 된다.

코드

#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long int
ll n, k, res;
void func() {
    ll left = 1, right = k;
    ll cnt;
    while (left <= right) {
        ll mid = (left + right) / 2;
        cnt = 0;
        for (ll i = 1; i <= n; ++i) {
            cnt += min(mid / i, n);
        }
        if (cnt < k) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
            res = min(res, mid);
        }
    }
}
 
int main() {
    scanf("%lld %lld", &n, &k);
    res = 9999999999999999;
    func();
    printf("%lld\n", res);
    return 0;
}