백준 - 1300번 : K번째 수 (C++)

풀이 방법 : 이분 탐색

숫자가 커서 다 검사하면 당연히 시간 초과가 뜬다.
이분탐색을 통해 숫자를 하나 골라서 그 숫자보다 작은 숫자가 몇 개 있는지 찾아내면 K번째 숫자가 될 수 있는지 알 수 있을 것이다.
이를 위해 한 줄씩 현재 숫자보다 작거나 같은 숫자가 몇 개인지 찾아야 한다.
한 줄에서 현재 숫자보다 작거나 같은 숫자의 최대 갯수는 N개일 것이다.

N이 4라고 하고 만약 8보다 작거나 같은 숫자의 갯수를 찾는다고 하면
1 2 3 4 -> min(8/1, N) = 4개
2 4 6 8 -> min(8/2, N) = 4개
3 6 9 12 -> min(8/3, N) = 2개
4 8 12 16 -> min(8/4, N) = 2개
가 될 것이다.

#include <iostream>

using namespace std;

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

	long long N, K;
	cin >> N >> K;
	
	long long Left = 1;
	long long Right = N * N;

	while (Left <= Right)
	{
		long long Mid = (Left + Right) / 2;
		long long Cnt = 0;

		for (int i = 1; i <= N; ++i)
		{
			Cnt += min(Mid / i, N);
		}

		if (K <= Cnt)
		{
			Right = Mid - 1;
		}

		else
		{
			Left = Mid + 1;
		}
	}

	cout << Left;
}