[백준] K번째 수 (복습 필요,,)

문제

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다.

출력

B[k]를 출력한다.

 

 

몇달 동안 몇번씩 시도하다가 막힌 문제....

어렵다

 

N*N배열을 오름차순 정렬했을때 K번째 수가 무엇인가를 묻는 문제입니다.

직접 오름차순 정렬해서 푸는건 말이 안되므로 

K번째 수가 S인지를 알아내는것 보다는

숫자S가 몇번째 수인지 알아내는게 빠릅니다.

배열의 숫자중에서 숫자 S보다 작거나 같은 숫자가 몇개 있는지 알아내는방법은

for(i:N)까지중에서 min(N,S/i)를 모두 더한 값입니다. >>>> 이게 시간을 줄이는 가장 중요한 포인트

i행에서 가장 많아봤자 N개이고, N개보다 적다면 S/i개 입니다. S/i가 N을 넘어갈 수 있으므로 N과 S/i중 작은 값이 되는겁니다.

 

따라서 숫자 S가 몇번째 수인지 O(N)만에 알아낼 수 있으므로,,,,,

이번에는 이분 탐색을 사용해서 숫자 S가 K번째에 도달할 때까지 숫자를 늘이고 줄이면서 탐색할겁니다.

 

left=1인데 right는 K가 되어야합니다. K번째 수는 항상 K보다 작거나 같기때문입니다. >>시간을 줄이는 두번째 포인트,,

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N, k;
int check(int x) {
	//x보다 같거나 작은 수의 개수
	int sum = 0;
	for (int i = 1; i <= N; i++) {
		sum += min(N, x/i);
	}
	return sum;
}
int main() {

	cin >> N >> k;
	int le = 1, ri = k, mid, ans = 0;
	while (le <= ri) {
		mid = (le + ri) / 2;
		int r = check(mid);
		if (k <= r) { 
			ans = mid;
			ri = mid - 1;
		}
		else if (k > r) {
			le = mid + 1;
		}
	}
	cout << ans;
}