문제

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

---

풀이

가장 단순하게 생각할 수 있는 방법은 다음과 같다.

1. 2차원 배열 A[i][j] 생성 → O(N^2)
2. N^2개의 원소를 오름차순으로 정렬 → O(N^2 * logN)
3. 1차원 배열 B에서 K번째 수 출력 → O(1)

그러나, N의 최대 크기가 10^5이므로 O(N^2)의 시간복잡도로는 반드시 시간초과가 발생한다.

그리고 배열 A 원소의 최댓값은 10^10이므로, int가 아닌 long long 타입의 배열이어야 한다.

그러면 메모리 크기는 최대 8B * 10^5 * 10^5 가 필요하므로 문제 제한 조건 (128MB) 보다 커서 메모리 초과가 발생한다.

따라서, 단순히 2차원 배열에 값을 저장하고 정렬하는 방식으로는 이 문제를 해결할 수 없다!

우리는 K번째 수를 구하는 더 효율적인 방법을 찾아야 한다.

이분 탐색

배열 A의 원소가 가질 수 있는 값 x의 최소, 최대 범위를 잡고 (1 ~ N^2)

x보다 작거나 같은 원소의 개수가

K개 이상이면, x의 값을 더 줄이고
K개 미만이면, x의 값을 늘리는 식으로

이분탐색을 진행한다.

그러면, x보다 작거나 같은 원소의 개수가 K개인 경우 x가 곧 K번째 수가 된다.

#include <iostream>
#include <string> 
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

ll N, K;

// x보다 작거나 같은 원소가 몇 개인가? 
ll getLowerCount(ll x) {
	ll sum = 0;
	for(int i = 1; i <= N; i++){
		sum += min(x / i, (ll)N);
	}
	return sum; 
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;
	
	ll left = 1, right = N * N;
	ll ans = 0;
	
	while(left <= right){
		ll mid = (left + right) / 2; 

		if(getLowerCount(mid) >= K){
			ans = mid; 
			right = mid - 1;
		}else{
			left = mid + 1; 
		}
	}

	cout << ans;
	
	return 0;
}

getLowerCount 함수의 시간복잡도는 O(N)

이분 탐색의 시간복잡도는 O(logN)

따라서, 최종적으로는 O(NlogN)의 시간복잡도여서 N이 최대 10만인 경우 TLE가 발생하지 않는다.