1654: 랜선 자르기

• toc {:toc}

문제 확인하기

풀이

최대 길이를 구해야 하기 때문에 내가 만든 랜선의 수와 필요한 개수의 같다고 바로 값을 반환하면 안 된다. 여러 경우가 나올 수 있기 때문이다. 11개가 필요할 때 802, 743, 457, 539 의 경우만 하더라도 200이 답이지만 199, 198, … 많은 답이 나올 수 있고 이 중 최대의 값을 가져야 한다. 때문에 같을 때에도 계속해서 mid+1로 갱신하며 start가 end보다 크게 되는 경우는 end가 더 이상 커질 수 없는 것과 마찬가지이기 때문에 end를 반환한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
 
int K, N;
int lan[10005];
 
int search(LL start, LL end){
    LL sum, mid;
    while(start <= end){
        sum = 0;
        mid = (start + end)/2;
        for(int i=0; i<K; i++){
            sum += lan[i] / mid;
        }
        if (sum >= N) start = mid + 1;
        else end = mid - 1;
    }
    return end;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(); cout.tie();
 
    LL val, high=0;
 
    cin >> K >> N;
    
    for(int i=0; i<K; i++){
        cin >> lan[i];
        if (high < lan[i]) high=lan[i];
    }
 
    cout << search(1, high) << '\n';
 
    
 
    return 0;
}