목차
실버3 : 이분 탐색 문제이다.
생각
이분 탐색 문제이다. 이전의 문제들과 마찬가지로, 값을 제시하고 그에 대한 분기를 만드는 것이 중요하다. 이 때, 어느 영역에서 답이 나오는지를 잘 체크하고, 답의 후보를 기록해두는 행위가 중요하다.
Code
#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<queue>
#include<functional>
using namespace std;
typedef long long ll;
ll K, N;
ll a[10001];
ll f(ll sug){
ll count = 0;
for (int i = 0; i < K; i++) {
count += (a[i]/sug);
}
return count;
}
int main(){
cin >> K >> N;
for (int i = 0; i < K; i++) {
cin >> a[i];
}
sort(a, a+K);
ll start = 1, end = (1LL << 31)-1, mid = 0, ans = -1;
while (start <= end) {
mid = (start+end)/2;
ll count = f(mid);
if (count < N) {
end = mid - 1;
} else {
ans = max(ans, mid);
start = mid + 1;
}
}
cout << ans << endl;
return 0;
}