K번째 수 백준 1300

문제

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

설명

위의 문제를 이해하는 데 시간이 걸렸다.

• n이 3일때를 생각해보자
  1 2 3
  4 5 6
  7 8 9
  일때 범위는 우선 1부터해서 n * n인 9까지이다

• 그렇다면 check(mid) >= k을 찾아야한다 찾고 나서 다시 값을 조정하는 이유는 정의때문이다.

• 만약 정렬해서 7번째 수이다 -> 자기보다 작거나 같은 갯수가 7개 이상인 수 중에서 가장 작은 수 이기에 조건을 만족해도 가장 작은 수로 만들기 위해서 값을 조정하는 것이다.

• 위의 check를 보다 x를 찾을려면 a[1][j] = min( x / i , n) -> a[i][j] = min(x / i, n)으로 찾아봐야한다 i가 증가할 수록2배씩 되기에 min속에서는 / i로 2배씩 줄여줬다...

• (check(mid) >= k == 자기보다 작거나 같은 갯수가 k개 이상인 수 중에서 가장 작은 수

소스

#include <bits/stdc++.h>

#define ll long long
using namespace std;

ll n, k, mid, ans;
ll check(ll x ) {
    ll ret = 0;
    for (ll i = 1; i <= n; i++) {
        ret += min(n, x / i);
    }
    return ret;
}
int main() {

    cin >> n >> k;
    //mid가 b[k]이다 

    ll le = 1, ri = n * n;
    while (le <= ri)
    {

        mid = (le + ri) / 2;

        if (check(mid) >= k) {
            ans = mid; //저장을 하지 않아서 22번라인의 mid가 if를 타지않아도 정답으로 흘러들어갈 수 있다!
            //왜 check(mid) == k 이면 끝내지 않냐? ->  1 2 2 3 3 4 6 6 처럼 6 b[k]번째의 답은 아닌데 숫자가 동일할 수도있다.
            ri = mid - 1;
        }
        else {
            le = mid + 1;
        }
    }

    cout << ans;
    return 0;
}