BOJ 1300 - K번째 수

이분탐색 문제다.

binarysearch나 lower_bound 등을 쓸 수 없는 이분탐색 문제 중 하나다.

 

[lo, hi] : 주어진 조건을 만족하는 값의 범위

//라이님의 블로그에선 [lo,hi)로 알려주셨지만 코드 짤 때 이게 더 편한 것 같다.

 

cnt+=min(n,mid/i) // i번째 행의 j번째 요소는 i*j 즉 i의 배수이므로 mid보다 작거나 같은 요소의 개수는 mid/i이다.(최대 n)

이부분을 생각하지 못하고 O(n)논리만  써서 자꾸 시간 초과가 났다.

 

if(cnt>=k) mid이하의 수가 k개 이상이라면 mid는 답이 될 가능성이 있다. (mid-1이하의 수가 k개 미만임이 보장돼야 확실한 답이 되지만 굳이 판단할 필요는 없다.) 따라서 mid+1은 답이 될가능성이 없다.

->hi = mid;

 

 

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int n, k; cin >> n >> k;
	int lo = 1, hi = 1e9 + 1;
	while (lo < hi) {
		int mid = (lo + hi) / 2;

		int cnt = 0;
		for (int i = 1; i <= n; i++) 
			cnt += (mid / i > n? n : mid/i);
		
		if (cnt >= k) hi = mid;
		else lo = mid + 1;

	}
	cout << lo << '\n';
}