[백준 알고리즘][C++] 이분 탐색(binary search) - 1300번 K번째 수

안녕하세요~

​

이번시간에는 1300번 K번째 수 문제를 풀어보려고 합니다.

 

www.acmicpc.net/problem/1300

1300번: K번째 수

명심하셔야 될 것은 일단 문제를 풀기 전에 코딩을 먼저 시작하지 마시고, 반드시 연습장으로 생각을 정리하고! 이 후에 생각이 맞는 것 같다고 확신이 되면 그 때 코딩을 시작하세요. 코드를 작성하면서 문제를 풀게되면 정리가 안된 상태기 때문에 코드 수정이 잦아지고, 정신이 없어지게 됩니다ㅠㅠ

그러니 반드시 노트에 어떻게 풀 것인지에 대한 정리를 다 하시고 코딩을 시작하시기 바랍니다!!

​

binary search 공부에 좋은 문제입니다.

#include <iostream>

using namespace std;
long long int N, K;
void solve()
{
	long long int  low = 1;
	long long int  high = K;

	while (low <= high)
	{
		long long int mid = (low + high) / 2;
		long long int sum = 0;
		for (int i = 1; i <= N; i++)
		{
			sum += min(N, mid / i);
		}
		if (sum < K)
		{
			low = mid + 1;
		}
		else
		{
			high = mid - 1;
		}
	}
	cout << low << endl;
}
int main()
{
	cin >> N >> K;
	solve();
}