[BOJ] 1300 K번째 수

문제보기

이분 탐색으로 left = 1, right = k를 시작으로 mid를 구하고 그 mid보다 작거나 같은 수의 갯수를 cnt에 저장한다.

cnt를 구하는 이유는 k번째 수를 구하기 위해서 k보다 작은 수의 갯수를 구할 필요가 있기 때문이다.

cnt(mid보다 작거나 같은 수)는 

min( mid / i, N)  --- (i 는 1부터 N까지)

를 전부 더한값이다.

그 이유는 a[i][j]에서 i행은 i의 배수들로 이루어져 있기 때문.

그때, i의 배수들이 N개를 넘을 수 없으므로 min함수를 이용한다.

그렇게 나온 cnt값(mid보다 작거나 같은 수의 갯수)이 k보다 작다면

left 값을 올리고

그렇지 않다면

result 에 mid값을 대입한 후 right값을 내린다.

---

#include <algorithm>

using namespace std;

int main(){

int k,N;

scanf("%d%d",&N,&k);

int l = 1, r = k, m,res;

while(l <= r){

m = (l + r) / 2;

int cnt = 0;

for(int i = 1;i<=N;i++){

cnt += min(m / i, N);

}

if(cnt < k){

l = m +1;

}else{

res = m;

r = m -1;

}

}

printf("%d\n",res);

}