백준 1300번: K번째 수

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

1300번: K번째 수

 

 

0. 알고리즘 분류

 이분 탐색

 

 

1. 문제

 

 

2. 풀이

 이분탐색 문제이다. 당연하게도, 문제에서 제시하는 순서대로 배열을 만들고 정렬하고 찾으면, 시간초과가 나온다. 필자는 도대체 어떻게 이분탐색을 쓰면 이 문제를 풀 수 있는지 생각해내지 못했다.. 결국 또 구글링이다. 구글링한 결과, 필자로서는 생각조차 못했던, 생각보다도 간단하게 풀리는 문제가 야속했다.

 

 left = 1, right = min(10^9, N*N)로 두고, mid = (left + right)/2 인 mid보다 작은 값의 개수를 세서 k번째 수를 이분탐색으로 찾는다.

 

 right 를 min(10^9, N*N)가 아닌 K로 두는 경우가 많던데, 코드가 간결할 수는 있겠지만 직관적으로 이해하기엔 어렵다고 생각해, 위와 같이 고쳤다. 10^10의 경우엔 overflow가 발생하므로, 최댓값은 10^9이다.

 

 

3. 코드

#include <bits/stdc++.h>

using namespace std;

int main() {
	int N, K;
	scanf("%d %d", &N, &K);

	int left = 1, ans;
	int right;
	
	if (N < 100*sqrt(100000)) {
		right = N*N;
	}
	else {
		right = 10000*100000;
	}
	
	while (left <= right) {
		long long cnt = 0;
		int mid = (left + right) / 2;
		
		for (int i = 1; i <= N; i++)
			cnt += std::min(mid / i, N);
			
		if (cnt < K)
			left = mid + 1;
		else
			ans = mid, right = mid - 1;
	}
	
	printf("%d", ans);

	return 0;
}