[백준oj] 1300번 k번째 수

www.acmicpc.net/problem/1300

1300번: K번째 수

---

 

O(logN)의 시간이 걸리는 이진탐색을 생각해봤다.

숫자의 범위는 항상 1~N*N까지 이다. 1~N*N의 중앙값을 m이라 설정한뒤에 m보다 작거나 같은 수의 개수를 구해준다. 이때 m>=i*j인 값을 카운트 해줘야되기때문에 m/i가 저 조건을 충족시키는 j의 숫자가 된다. 하지만 한 행에서 m/i의 개수가 N이상으로 커질 수 없기 때문에 min(m/i,N)을 해준다.

이 결과에 따라 이진탐색을 해주면 된다.

 

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

int main() {
	int n, k;
	cin >> n >> k;

	int left = 1;
	int right = n*n;
	int answer = 1;
	while (left <= right) {
		int m = (left + right) >> 1;
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			cnt += min(m / i, n);//행마다 m보다 작은 값 카운트
		}
		if (cnt < k) {
			left = m + 1;
		}
		else {
			answer = m;
			right = m - 1;
		}
	}
	cout <<  answer;
	return 0;
}