백준[1654] 랜선 자르기

해당 문제는 이진 탐색을 살짝 응용한 문제인데 전체적인 코드를 짜기는 쉬웠지만..

특수한 케이스들이 존재해서 해당 반례를 찾느라 푸는 시간이 많이 늦어졌다..ㅠ

 

 

#include <bits/stdc++.h>

long long findcuttingSize(vector<long long> &arr,long long N, long long start, long long end){
    long long result = 0;
    while(start<=end){
        long long mid = (start + end)/2;
        long long total = 0;

        for(int i=0;i<arr.size();i++)
            if (arr[i] >= mid){
                total += arr[i] / mid;
            }
      
        if(total >= N){
            result = mid;
            start = mid + 1;
        }
        else{
            end = mid - 1;
        }
    }
    return result;
}

void cuttingLan(){
    long long K,N;
    cin>>K>>N;
    
    vector<long long> arr;
    long long max = 0;
    
    for(int i=0;i<K;i++){
        long long k;
        scanf("%lld",&k);
        if(max<k)
            max = k;
        arr.push_back(k);
    }
    sort(arr.begin(),arr.end());

    printf("%lld\n",findcuttingSize(arr, N, 1, max));
    
}

 

 

유용한 반례

/*
 // 최솟값이 아닌 최댓값 반례
 3 4
 2
 19
 6
 ans: 6
 
 // 입력한 N에 정확하게 total값이 나오지 않는 경우
 4 18
 16
 16
 16
 16
 ans: 3
 
 */