[BS] 백준 1300 k번째 수

• n 제한도 잘 생각해야하고 잘 생각하자
• 다시한번 상기시키지만 left 조건에 = 없이 써야한다. 3079 문제 참고

---

K번째 수 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	2302	705	522	35.104%

문제

세준이는 N*N크기의 배열을 만들었다. (배열의 방 번호는 1부터 시작한다.)

그 배열을 A라고 했을 때, 배열에 들어가는 수는 A[i][j] = i*j 이다.

세준이는 이 수를 일차원 배열 B에 넣으려고 한다. 그렇게 되면, B의 크기는 N*N이 될 것이다. 그러고 난 후에, B를 정렬해서 k번째 원소를 구하려고 한다.

N이 주어졌을 때, k번째 원소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, n2)보다 작거나 같은 자연수이다.

출력

k번째 원소를 출력한다.

예제 입력 1 

3

7

예제 출력 1 

6

---

#include <iostream>

#include <limits.h>

#include <algorithm>

using namespace std;

typedef long long ll;

const ll Imax = 1000000000000000000ll;

int main(void)

{

       ll n, k;

       cin >> n >> k;

       ll left = 0;

       ll right = min(n*n, 1000000000ll);

       while (left <= right) {

              ll mid = (left + right) / 2;

              ll cnt = 0;

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

                     cnt += min(mid / i, n);

              }

              if (cnt < k) {

                     left = mid + 1;

              }

              else {

                     right = mid - 1;

              }

       }

       cout << left << endl;

       return 0;

}