[백준/BOJ] 백준 1300번 : K번째 수

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

1300번: K번째 수

이분 탐색으로 문제를 해결했다. 각 행마다 확인하는 수 보다 작은 수가 몇 개 있는지 개수를 구해서 이분 탐색을 진행했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

int n;
int k;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	cin >> k;

	int left = 1;
	int right = 1000000000;
	int result = -1;

	while (left <= right)
	{
		int mid = (left + right) / 2;
		long long check = 0; //mid보다 작은수들의 개수

		//각 행마다 확인한다
		for (int i = 1; i <= n; i++)
		{
			int this_row = i;

			//i행에 mid보다 작은 수 몇개 있는지 확인
			int this_check = min(n, (mid / i));

			if (this_check == 0)
				break;

			check += (long long)this_check;
		}


		if (check >= k)
		{
			result = mid;

			right = mid - 1;
		}

		else
		{
			left = mid + 1;
		}
	}

	cout << result;

	return 0;
}