문제
풀이
이분 탐색을 위해 1을 left로 N x N 을 right로 먼저 시작한다. mid = (left+right)/2; 로 설정하여, mid보다 작거나 같은 수가 몇개인지 셉니다. 그 숫자가 K보다 크다면 범위를 줄이기 위해서 right = mid - 1 로 설정하고 그 숫자가 K보다 작다면 범위를 늘리기 위해서 left = mid + 1로 설정합니다. 이것을 반복하여 결국 while(left<=right)를 빠져 나올 때, left를 출력합니다. mid보다 작거나 같은 수가 몇 개인지 세는 알고리즘은 결과적으로 O(N)인데, 각 행에서 x보다 작은 값의 개수의 최대값은 i: 1 ~ N(=행을 의미), cnt = min(x/i, N);가 됩니다. 각 행의 값들은 ixj(j = 열, 1, 2, 3, 4…)이 됩니다. 결국 ixj <= x를 만족하는 것을 찾으면 되어 결과적으로 j <= x/i 이 성립하게 됩니다. 이는 1부터 x까지의 수가 모두 행에 있을 때를 가정했을 때 갯수이므로, x/i이 N보다 크다면 N값을 출력하게 합니다. 결과적으로 모든 행의 cnt들을 더하면 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>
using namespace std;
long long N, M;
long long cnt(long long num){
long long sum = 0;
for(long long i = 1; i<=N; i++){
sum += min(num/i, N);
}
return sum;
}
int main(){
scanf("%lld", &N);
scanf("%lld", &M);
long long left = 1;
long long right = N*N;
while(left <= right){
long long mid = (left + right) / 2;
if(cnt(mid) >= M){
right = mid - 1;
}
else left = mid + 1;
}
printf("%lld\n", left);
}
