[C++] 백준 1300 K번째 수

#include <iostream>
#include <iostream>
#include <algorithm>
#include <vector>
 
long long N = 0;
long long k = 0;
long long Low = 0;
long long High = 0;
long long Mid = 0;
long long count = 0;
 
long long countOrder(long long x)
{
	long long sum = 0;
 
	for (int i = 1; i <= N; ++i)
	{
		sum += std::min(x / i, N);
	}
 
	return sum;
}
 
int main()
{
	std::cin >> N >> k;
 
	k = std::min((long long)1000000000, k);
 
	Low = 1;
	High = N * N;
 
	while (Low <= High)
	{
		Mid = (Low + High) / 2;
 
		count = countOrder(Mid);
 
		if (count >= k)
		{
			High = Mid - 1;
		}
 
		else
		{
			Low = Mid + 1;
		}
	}
 
	std::cout << Low;
 
	return 0;
}

이분 탐색을 이용해서 푸는 문제

제일 헷갈리는 게 어떤 순서에 따라서 찾을 수 있는가였는데

min(x / i, N)으로 계산할 수 있었다.

모든 행마다 x크기에 i로 나눠서 그게 N보다 크다면 N (열의 갯수 만큼 더하고)

N보다 작다면  x/i가 몇 열까지 크기가 큰가를 정할 수 있습니다.