백준 #1300 K번째 수


BOJ #1300 - K번째 수

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

# 문제 분류

이분 탐색

풀이 접근 방법


이분 탐색보다 min(mid / i, N) 떠올리는건 세시간 줘도 못할듯 ㅋㅋ ㅠ


#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const ll MOD = 1e9 + 7;
const int stMAX = 1 << 18;
const int INF = 1e9;
int N, k;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> k;

    int l = 1, r = 1e9;
    while (l <= r) {
        int mid = l + r >> 1;

        ll cnt = 0;
        for (int i = 1; i <= N; i++) {
            cnt += min(mid / i, N);
        }

        if (cnt < k) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    cout << l;
}