[백준 1300] k번째 수

요구사항

n*n 행렬에서 k번째 수를 구하여라

 

풀이

전부 탐색하면 시간초과가 난다

현재 선택한 mid보다 작은 수자의 갯수를 1~n까지 탐색하면서 찾아보자

1일때는 mid보다 작은것은 1, 2, 3 ,4~~mid, mid+1 ,mid +2 ,,, n중에서 mid까지가 mid보다 작은 수이다 이것은 mid 개 있다

2일때 mid보다 작은 것은 2 4 6 8 ,,,,, mid ,mid+2,mid+4 ,,,,,n 까지 중 mid보다 작은 수는 mid/2 개 가 있다

3일때는 mid/3 이다

mid/i 를 해서 정수가 나오는 거 까지는 mid보다 작다고 할 수 있다

 

cnt의 개수를 구해서 원하는 k보다 작다면 low를 증가 k보다 크다면 high를 감소 시켜며

k번째 수를 찾는다

 

아래 블로그를 참조하였다 어렵다

 

https://jaimemin.tistory.com/988

 

#include <iostream>
#include <algorithm>

using namespace std;
int n, k;
int ans = 0;
int main() {
	scanf("%d%d", &n, &k);
	int low = 0;
	int high = k;

	while (low <= high) {
		int mid = (low + high) / 2;
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			cnt += min(mid / i, n);
		}
		if (cnt < k) {
			low = mid + 1;
		}
		else {
			ans = mid;
			high = mid - 1;
		}
	}
	cout << ans << endl;
}