[BaekJoon] 1654번 랜선 자르기

• 이 글은 C++로 풀이를 작성하였습니다.

문제

 

예시

 

풀이

• 이 문제는 이분탐색을 활용한 Parametric Search 알고리즘을 사용해야 합니다.
• 1부터 최대 길이를 양쪽으로 하여 절반씩 길이일 경우에 원하는 랜선의 갯수가 되는지 확인하여 s와 e를 조정합니다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int n,k;
    cin>>n>>k;

    int arr[10000];
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }

    long long s = 1;
    long long e = 1;
    for(int i=1;i<=31;i++){
        e*=2;
    }
    e-=1;

    long long mid;
    while(s<e){
        mid = (s+e+1)/2;

        int cnt = 0;
        for(int i=0;i<n;i++){
            cnt+=(arr[i]/mid);
        }

        if(cnt<k){
            e = mid-1;
        }else{
            s = mid;
        }
    }
    cout<<s;
}