[BOJ/C++] 1300 K번째 수

이진 탐색으로 문제를 해결할 수 있지만 아이디어를 떠올리기 어려웠던 문제입니다.

우선 이진 탐색을 써야한다는 것 자체를 떠올리는게 어려웠습니다.

그리고 K번째 수보다 작거나 같은 값이 최소 K개 존재한다는 것과 각 행렬을 T로 나눈 몫과 N의 최솟값이 T보다 작은 수의 개수라는 것이 어려웠습니다.

• 최초의 중앙값은 (1+7)/2 = 4로 설정합니다.
• 중앙값보다 작거나 같은 수의 개수는 min(middle/i, N)으로 계산하고 N은 행의 개수입니다.

• start>end가 되었을 때 이진 탐색을 종료하고 이때 업데이트 된 start가 정답입니다.

// boj g1 1300
// K번째 수

// 아이디어가 굉장히 어려웠던 문제
// K번째 수보다 작거나 같은 값이 최소 K개 존재한다
// 각 행렬을 T로 나눈 몫과 N의 최솟값이 T보다 작은 수의 개수이다

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

int main(void)
{
    ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

    int N, K;
    cin >> N >> K;

    int left=1;
    int right=K;
    int mid;

    while(right>=left)
    {
        int sum=0;
        mid=(left+right)/2;
        for(int i=1; i<=N; i++)
        {
            sum+=min(N, mid/i);
        }

        if(K>sum)
            left=mid+1;
        else
            right=mid-1;
    }

    cout<<left;

    return 0;
}