[백준 1300번 / C++] K번째 수

이분 탐색 문제이다. 

 

처음에 접근할 때 벡터를 생성하고 i*j 값을 push_back 해서 오름차순으로 정렬한다. 
k 위치에 해당하는 벡터의 원소를 출력한다. 

 

이렇게 해선 안된다.

 

N은 최대 10^5 이며 NxN 이기에 최악의 경우 100억의 벡터를 생성해야하는데 이러면 메모리 초과다. 

그렇기 때문에 따로 벡터나 배열을 생성하지 않고 이분탐색으로만 확인하는 과정을 찾아보자. 

 

1. low 에는 1 의 값을 저장하고 high 값에는 최악의 경우 10000000000(100억) 의 값을 저장한다. 

 

2. 이차원 배열에는 i 행과 j 열이 있는데 각 원소는 i와 j의 곱의 결과가 저장되어있다. 현재 mid 값은 갱신되는 기준값이며 해당 기준값에서 i를 나눠준 몫이 j 값이다. 그렇기 때문에 i 행에서 mid값보다 작거나 같은 원소의 개수는 열에 해당하는 j 이며 해당 값을 counting 해준다. 

 

3. 개수의 대소 비교를 통해 끝점을 갱신해나간다. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 
typedef long long ll; 
int main() {

	ios::sync_with_stdio(false); 
	cin.tie(0); cout.tie(0); 
	ll n, k; 
	cin >> n >> k;	
	ll l, h; 
	l = 1; 
	h = 10000000000; 
	int result = 0; 
	while (l <= h) {
		ll mid = (l + h) / 2; 
		ll cnt = 0; 
		for (int i = 1; i <= n; i++) {
			cnt += min(mid / i, n); 
		}
		if (k <= cnt) {
			result = mid; 
			h = mid - 1; 
		}
		else {
			l = mid + 1; 
		}
	}
	cout << result; 
}

 

1300번: K번째 수