난이도 | 골드2 |
시간제한 | 2초 |
메모리 제한 | 128MB |
문제에서의 B[k] = x
는 B
배열의 k
번째 인덱스가 x
라는 의미이다. 이를 반대로 해석하면 x 보다 작거나 같은 element의 개수는 k개
라는 의미로도 해석이 가능하다. (B배열은 오름차순으로 정렬되어 있기 때문이다)
그러면 우리는 x
의 값을 조정하면서(이분탐색) 문제에서 원하는 정답을 찾으면 된다.
int k = 0;
for (int i = 1; i <= n; i++) {
k += min(n, x / i);
}
left
: 1 right
: n x n
위에서 구한 k
값이 K(입력값)
보다 크다면, x(mid) 보다 작거나 같은 element의 개수가 K(입력값)보다 많다는 의미
이므로 왼쪽 영역(x(mid)
값이 줄어드는) 영역을 탐색하면 된다.. 그 반대의 경우엔 오른쪽 영역을 탐색하도록 한다.
추가적으로 왼쪽 영역을 탐색할 때의 mid
값은 ans
의 후보가 될 수 있으므로 ans = mid
를 해줘야 한다.
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
long long k;
cin >> k;
long long ans = 1;
long long left = 1;
long long right = n * n;
while (left <= right) {
long long middle = (left + right) / 2;
long long cnt = 0;
for (long long i = 1; i <= n; i++) {
cnt += min(n, middle / i);
}
if (k <= cnt) {
right = middle - 1;
ans = middle;
}
else {
left = middle + 1;
}
}
cout << ans;
return 0;
}