백준 1300번 : K번째 수 - 이분 탐색 C++

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

1300번: K번째 수

 

숫자 범위가 굉장히 크다.

하나씩 다 따져보다간 시간이 너무 오래 걸린다.

바운더리 컨디션을 생각해보면서 이분탐색을 시행해야 문제를 해결 할 수 있다.

#include <bits/stdc++.h>
using namespace std;

int n, k;

int main() {

    cin >> n >> k;

    int st = 1, en = k , ans;

    while(st <= en){
        int mid = (st + en)/2;

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

        if(cnt >= k){
            ans = mid;
            en = mid - 1;
        }
        else{
            st = mid + 1;
        }
    }

    cout << ans << '\n';


    return 0;
}