Search
Duplicate

랜선 자르기 (1654)

생성일
2021/03/20 18:19
태그

문제

풀이

주어진 길이로 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++
복사