랜선자르기

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
ll N,M,high;
vector<ll> arr;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for(int i=0;i<N;i++)
    {
        int a;
        cin >> a;
        arr.push_back(a);
        high=max(high,arr[i]);
    }
    /* left가 0이면 N=1,K=1, input=1 일 때 나누는 수인 mid가 0이되어서
        런타임 에러가 발생한다 */
    ll left=1, right=high;
    ll ans=0;
    while(left<=right)
    {
        ll tot = 0;
        ll mid = (left + right)/2;
        for(auto a : arr)
            tot += a/mid; // 항상 mid가 0이되는 예외가 없는지 확인해줘야 함
        if(tot < M)
            right = mid - 1;
        else
        /* tot이 M보다 크거나 같을때 일단 지금까지 랜선 길이를 저장하고
           더 큰값을 검사하러 이동 */
        {
            ans = max(ans,mid);
            left = mid + 1;
        }
    }
    cout << ans;
    return 0;
}

• 로직
  : 최적의 랜선 길이를 찾는 탐색을 이분탐색으로 하여 찾는다
• 주의
  : 이분탐색을 할 때 항상 나누는 수인 mid가 0이되는 경우를 찾아 예외처리를 해주어야 한다
  (본 문제
  : N=1, M=1, input=1일 때 mid가 0이되므로 최초left를 1로 초기화)