[백준 c++] 1645 랜선 자르기

문제

https://www.acmicpc.net/problem/1654
길이가 제각각인 K개의 랜선을 잘라서 N개로 만들고 싶다.
K개의 랜선의 정보가 주어진다.
이 때 N개로 만들 수 있는 랜선 길이의 최대값을 구해라.

---

풀이

이분탐색을 이용한 풀이

divisionByZero 오류가 날 수 있기 때문에 초기 low = 1

이분탐색에서 특정 조건을 만족하는 값을 찾을 때는
low나 high값을 1씩 조절해서 최적값을 찾을 수 있다.

이 문제에서는 n개로 만들 수 있는 랜선의 최대 길이이므로
cnt(랜선들을 mid값으로 나눈 몫의 합) == n 이더라도
더 큰 만족하는 값이 있는지 찾아야하므로

        if (cnt >= n)
        {
            low = mid + 1;
            ret = max(ret, mid);
        }

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long n, k, t, mid, high, low, cnt, ret;
vector<long long> v;
int main()
{
    cin >> k >> n;

    for (int i = 0; i < k; i++)
    {
        cin >> t;
        v.push_back(t);
    }
    
    sort(v.begin(), v.end());

    high = v.back();
    low = 1;
    
    while (low <= high)
    {
        mid = (high + low) / 2;
        cnt = 0;
        for (long long i : v)
            cnt += i / mid;
        if (cnt < n)
            high = mid - 1;
        if (cnt >= n)
        {
            low = mid + 1;
            ret = max(ret, mid);
        }
    }
    
    cout << ret;
}