1654) 랜선 자르기

문제 요약

랜선의 갯수 k와 필요한 랜선의 갯수 n이 있을 때, k개의 랜선들을 잘라서 같은 크기의 n개의 랜선을 만들 수 있다고 할 때, 랜선의 최대 길이를 구하는 문제

풀이

랜선의 갯수는 모든 기존랜선길이/m (m= 랜선의 길이) 를 k개의 랜선에 적용해 모두 더한 값이다. 이때 길이 m이 최대가 되어야 한다. 이는 탐색 문제로 볼 수 있는데, 랜선 갯수가 n이 될 수 있는 사이즈들 중 최대값을 찾으면 된다.
이진탐색을 이용해서 min은 랜선 갯수가 n과 같거나 크도록, max를 랜선 갯수보다 작도록 한다면, min과 max가 바로 옆에 놓일때, min의 값이 구하고자 하는 값이 된다.
*그림 설명

잘 알아볼 수 있을지 모르겠지만... 여기서 sum은 랜선 갯수의 총합이고 sum배열의 인덱스는 랜선의 길이를 뜻한다. 즉 가장 오른쪽 n의 index를 구해야 한다.
핵심은 binary search에서 min의 값을 n보다 같거나 큰 요소의 인덱스 값으로,max의 값을 n보다 큰 요소의 인덱스 값으로 유지해야 한다.

코드

#include<iostream>
#include<vector>
using namespace std;
void cal1(vector<unsigned long > &len, unsigned long *max,unsigned long *min, unsigned long* size, int n);
int cal2(vector<unsigned long > &len, unsigned long size);
int main(){
    int k, n;
    unsigned long max =0, min, tmp, size;
    cin>>k;
    cin>>n;
    vector<unsigned long > len;
    for(int i =0;i<k;i++){
        cin>>tmp;
        len.push_back(tmp);
        if(tmp>max)
            max = tmp;
    }
    min = 1;
    size = max;
    cal1(len, &max,&min, &size, n);
    cout<< min<<endl;
}

void cal1(vector<unsigned long > &len, unsigned long *max,unsigned long *min, unsigned long* size, int n){
    int sum = cal2(len, *size);
    if(sum<n&&(*min<(*max-1))){
        *max = *size;
        *size = *min +(*max-*min)/2;
        cal1(len,max, min, size, n);
    }
    else if(sum>=n&&*min<(*max-1)){
        *min= *size;
        *size = *min +(*max-*min)/2;
        cal1(len, max, min, size, n);
    }   
    return;
}

int cal2(vector<unsigned long > &len, unsigned long size){
    int sum =0;
    for(int i=0;i<len.size();i++){
        sum += len[i]/(size);
    }
    return sum;
}