BOJ 1300 K번째 수

 
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <functional>

typedef long long int ll;
using namespace std;
#define INF 1234567890
#define N 200000

const int LIMIT = 1e+9;
int n, k;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> k;

	int left = 1, right = k, res = 0;
	while (left <= right) {
		ll cnt = 0;
		int mid = (left + right) / 2;
		for (int i = 1; i <= n; i++) {
			cnt += min(mid / i, n);
		}
		if (cnt < k) left = mid + 1;
		else {
			res = mid;
			right = mid - 1;
		}
			
	}
	cout << res;

	return 0;
}



K번째 수

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 4989 1599 1174 36.768%

문제

세준이는 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

출처

  • 문제를 번역한 사람: baekjoon
  • 빠진 조건을 찾은 사람: mystika