백준 1300번 문제 K번째 수 풀이

백준저지 1300번 문제 "K번째 수" 문제 풀이입니다.

https://www.acmicpc.net/problem/1300

1300번: K번째 수

 

바이너리 서치로 풀이하였습니다.

 

N이 주어졌을 때, 특정 수 x보다 작거나 같은 수의 개수를 O(N)만에 계산할 수 있는데, 이를 이용하여

x보다 작거나 같은 수의 개수가 K와 비슷해질때까지 바이너리 서치를 합니다.

 

x보다 작거나 같은 수의 개수를 num(x) 라 할 때

 

바이너리 서치와 약간 다른 점은, K와 완전히 같은 num(x)가 존재하지 않을 수 있습니다.

 

따라서 K보다 큰 num(x) 중 최소 값을 갖는 x를 구해야 하며, num(x) == num(x+1) == ... == num(x+a) 와 같이 같은 값들을 가지는 num(x)들이 있을 수 있습니다. 이들 중에서는 가장 작은 x값이 정답이 됩니다.

 

num(x) == num(x+1) == ... == num(x+a)와 같은 관계에서는 x는 실제 N*N 매트릭스에 존재하는 값이지만, x+1은 존재하지 않는 값이기 때문입니다.

 

코드는 아래와 같습니다.

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll num(ll v, ll N) {
    ll ret = 0;
    //v보다 작거나 같은 원소 개수를 리턴함
    for (int i = 1; i <= N; i++) {
        ret += min(N, v / i);
    }
    return ret;
}
ll solve(ll N, ll K) {
    //binary search 할 예정인데
    // K보다 크거나 같은 값 중 최소 값 구할 예정. (중복 수 있을 수 있으므로)
    // K와 같은 값이면 그중에 가장 작은 값
    ll l = 1, r = N*N;
    while (l < r) {
        ll m = (l + r) / 2;
        long long n = num(m, N);
        if (n == K) {
            ll v = m - 1;
            while (n == num(v, N)) {
                v--;
            }
            r = v + 1;
            break;
        }
        else if (n > K) {
            r = m;
        }
        else if (n < K) {
            l = m + 1;
        }
    }
    return r;
}

int main() {
    ll N, K; cin >> N >> K;
    cout << solve(N, K) << endl;

    return 0;
}