boj1300 K번째 수

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

1300번: K번째 수

 

 

책정된 난이도에 비해서 어렵다... 하지만 코드가 짧다. 진짜 아이디어 싸움이다.

 

 

힌트 :

low = 0 , high = n*n+1 를 하고 이것의 mid 값을 기준으로 count 하여 count 값이 k번째 보다 작은지 큰지를 판별하면 된다.

 

 

 

 

더 힌트 : count를 세는 방법을 O(n)으로 알 수 있다. 행렬 특성을 잘 살리면 된다.

각 행별로 count는 mid/X행 이지 않을까?

 

 

 

 

 

답

#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<int, int>
#define ll long long int
using namespace std;
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    ll n, k;
    cin >> n >> k;
 
 
    ll low = 1;
    ll high = n * n + 1;
    ll mid;
 
    while (low < high)
    {
        mid = (low + high) / 2;
        ll count = 0;
        for (int i = 1; i <= n; i++)
            count += (ll) min(mid / i, n);
        
        if (count < k)
            low = mid + 1;
        else
            high = mid;
    }
 
    cout << high;
 
}