뚝배기 터진 문제_boj
boj1300 K번째 수
헐랭미
2020. 6. 22. 17:35
https://www.acmicpc.net/problem/1300
책정된 난이도에 비해서 어렵다... 하지만 코드가 짧다. 진짜 아이디어 싸움이다.
힌트 :
low = 0 , high = n*n+1 를 하고 이것의 mid 값을 기준으로 count 하여 count 값이 k번째 보다 작은지 큰지를 판별하면 된다.
더 힌트 : count를 세는 방법을 O(n)으로 알 수 있다. 행렬 특성을 잘 살리면 된다.
각 행별로 count는 mid/X행 이지 않을까?
답
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
28
29
30
31
32
33
34
35
36
37
|
#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<int, int>
#define ll long long int
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
ll n, k;
cin >> n >> k;
ll low = 1;
ll high = n * n + 1;
ll mid;
while (low < high)
{
mid = (low + high) / 2;
ll count = 0;
for (int i = 1; i <= n; i++)
count += (ll) min(mid / i, n);
if (count < k)
low = mid + 1;
else
high = mid;
}
cout << high;
}
|
cs |