1654 랜선 자르기

1654 랜선 자르기

1. low=0, 주어지는 길이들의 최대값을 찾아 high로 놓는다.

2. mid로 나눈값들의 합이 k보다 크거나 같은경우 최대값을 갱신해준다.

#include <iostream>
#define ll long long
using namespace std;
 
ll n, k, res;
ll a[10001];
 
ll max(ll a, ll b) {
    return (a > b) ? a : b;
}
 
bool search(ll mid) {
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += a[i] / mid;
    }
    return (ans >= k) ? true : false;
}
 
int main() {
    scanf("%lld %lld", &n, &k);
 
    ll low = 0;
    ll mid = 0;
    ll high = 0;
    res = 1;
 
    //high에 길이의 최대값 저장
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
        high = max(high, a[i]);
    }
 
    while (low <= high) {
        mid = (low + high) / 2;
        if (mid == 0) break; // mid==0 이면 종료, base-> res=1
 
        //이분탐색
        if (search(mid)) {
            res = max(res, mid);
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    printf("%lld\n", res);
}