K번째 수
[문제 링크] (https://www.acmicpc.net/problem/1300)
문제에서 알 수 있듯이 N은 최대 10^5의 수를 가질 수 있다.
2차원 배열에 있는 값을 1차원 배열에 넣어서 정렬하기에는 N이 너무 크다.
따라서 1차원 배열로 만들려고 하면 안된다.
수는 n x n개까지 있을 수 있고, 그 n x n개중에서 k번째 원소를 구하는 것이다.
예를 들어, test case를 보자
n = 3이기 때문에,
3 x 3 행렬이
1 2 3
2 4 6
3 6 9
이런 식으로 만들어 진다.
이것을 1차원 배열을 만들면 -> 1 2 2 3 3 4 6 6 9 로 만들어진다.
7번째 수는 6이다.
생각을 해보면, k번째 수라는 것은 정렬되어 있기 때문에
자기보다 작은 값이 k-1개 있다는 것이다.
또, 행마다 행의 배수로 수가 나열되어 있다는 것을 알 수 있다.
이제 답을 구하기 위해서, 이진 탐색을 실행 한다.
또, mid값을 행의 번호로 나눈 몫 = mid값보다 작거나 같은 값의 개수 이다.
이렇게 개수를 다 더해서 k랑 비교를 해준다.
이렇게 k번째 원소를 구하면, O(10^5 x log 10^5) 가 된다.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
ll n, k;
int main() {
ll before = 0, after = 0, mini = 1e9;
cin >> n >> k;
ll s = 1, e = n * n;
while (s <= e) {
ll cnt = 0;
ll mid = (s + e) / 2;
for (int i = 1; i <= n; i++) {
cnt += min(n, (mid / i));
}
if (cnt < k) {
before = cnt;
s = mid + 1;
}
else {
e = mid - 1;
mini = min(mini, mid);
}
}
cout << mini << "\n";
}
