06.09. K번째 수 [Binary Search & Parametric Search][백준 1300]

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

1300번: K번째 수

 

Algorithm classification : Binary Search, Parametric Search

 

06.09.1. Problem

Sejun created an array A of size N×N. The number in the array A[i][j] = i×j. If we put this number into a one-dimensional array B, the size of B is N × N. Let's find B[k] when B is sorted in ascending order.

The indices of arrays A and B start at 1.

 

 

06.09.2. Input limit

The first line gives the size N of the array. N is a natural number less than or equal to 10^5. In the second line, k is given. k is a natural number less than or equal to min(10^9, N^2).

 

 

06.09.3. Output

Print B[k].

 

 

06.09.4. Solution

N의 최댓값을 잘 보시면 원하는 2차원 배열을 다 만들 수 없을 겁니다. 이분 탐색으로 구하고자 하는 것은 B[k]이니 B[k]를 MID값으로 탐색하면서 이보다 작은 수가 배열에 몇 개인지 CHECK하면 됩니다.

	long long a[(n+1) * (n+1)], k = 0, i, j;
	for(i = 1; i <= n; i++){
		for(j = 1; j <= n; j++){
			a[++k] = i * j;
		}
	}
	sort(a, a+(n+1)*(n+1));
	
	printf("%lld", a[index]);

 

이렇게 구현한다면 8Byte * 10^5 * 10^5 = 80GB입니다. 이 문제 하나 풀잡시고 80GB면 희생이 너무 크네요. 그렇기엔 이 문제가 제 인생에서 크게 중요하진 않거든요. 이분탐색이라 큰 의미가 있을까 싶습니다만 RIGHT도 좀 작은 수로 시작하면 좋겠죠.(저렇게 상한을 잡아둘 때는 확실한 수학적 근거가 있어야 합니다.) 생각해보면 CHECK 부분이 O(N)이기 때문에 N의 크기가 큰 test case일 경우 RIGHT를 저렇게 줄여놓고 시작하면 효과가 있을 겁니다.

	for(i = 1; i <= n; i++){
		if(i*i >= index){
			right = i * i;
		}
	}
	while(left <= right){
		mid = (left + right) / 2;
		temp = 0;

		for(i = 1; i <= n; i++){
			temp += min(mid / i, n);
		}
		if(temp >= index){
			result = mid;
			right = mid - 1;
		}
		else{
			left = mid + 1;
		}
		
	} 
	
	printf("%lld", result);