핵심은 이분 탐색 시 mid 값보다 작은 수의 개수를 구하도록 하는 것이다.
이 때 mid 값보다 작은 수의 개수를 구하는 방법은,
각 행을 돌며 mid / i 값과 각 행의 최대 개수인 N을 비교하는 것이다.
행 방향 값들은 모두 정렬되어 있기 때문에 이 방법을 사용할 수 있는 것이다.
예를 들어 4*4
행렬은 아래와 같다.
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16
만약 mid가 3이라면, 1행에서 3보다 작은 값은
1*1
, 1*2
, 1*3
. 즉, 3/1
개와 같다.
2행에서 3보다 작은 값은 3/2
=1
개이고,
..
4행에서 3보다 작은 값은 3/4
=0
개이다.
이렇게 구한 모든 개수를 더하면 mid인 3보다 작은 원소의 개수를 구할 수 있다.
총 개수가 K보다 작을 때와 그렇지 않을 때로 구분하여 계산하면 된다.
#include <iostream>
#include <algorithm>
using namespace std;
long long N, K, ans;
void solution() {
long long l = 1;
long long r = N * N;
long long m, cnt;
while (l <= r) {
m = (l + r) / 2;
cnt = 0;
for (long long i = 1; i <= N; i++)
cnt += min(m / i, N);
if (cnt < K) {
l = m + 1;
}
else {
ans = m;
r = m - 1;
}
}
return;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> K;
solution();
cout << ans;
return 0;
}