문제
풀이
•
주어진 길이로 k개 만들기 가능 -> 더 긴길이로 도전 (오른쪽)
•
주어진 길이로 k개 만들기 불가능 -> 더 짧은 길이로 도전 (왼쪽)
구현
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int k;
int n;
vector<long long> lines;
void pre() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
void input() {
pre();
cin >> k >> n;
lines.resize(k);
for(int i = 0; i < k; i++)
cin >> lines[i];
}
long long check(long long len) {
//주어진 길이로 k개 만들기 가능 -> 더 긴길이로 도전 (오른쪽)
//주어진 길이로 k개 만들기 불가능 -> 더 짧은 길이로 도전 (왼쪽)
long long num;
num = 0;
for(int i = 0; i < k; i++)
num += lines[i] / len;
return (num < n);
}
long long rec(long long left, long long right) {
long long mid;
mid = (left + right) / 2;
if (right <= left + 1)
return (mid);
return (check(mid) ? rec(left, mid) : rec(mid, right));
}
void solve() {
long long max_line;
for(int i = 0; i < k; i++)
max_line = max(max_line, lines[i]);
cout << rec(0, max_line + 1) << endl;
}
int main() {
input();
solve();
return (0);
}
C++
복사