백준 1654 - 랜선 자르기

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

문제 설명

---

자체적으로 K개의 랜선을 가지고 있으며 K개의 랜선은 길이가 제각각이다. 이때 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. (자르고 남은 랜선은 버리며 이미 자른 랜선은 붙일 수 없다.)

[가정]

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자.

 

 

접근 방법

---

이분 탐색을 많이 풀어보지 않아서 풀어보았습니다 ^^ 이분 탐색으로 접근하며 다음고 같은 메커니즘으로 코드를 작성했습니다.

 

1. 입력 받은 전선의 길이 중 최대 길이를 high로 설정하고 자르는 전선의 길이가 존재해야하므로 low는 1로 잡습니다.(못자르는 경우는 없다고 명시 되어있으므로)

2. 이분 탐색을 진행하면서 mid에 대해 조건을 충족하는지 체크합니다. 이때 조건에 부합된다면 전선으 길이를 늘리고 반대라면 전선의 길이를 줄입니다. 이후 해당 조건을 만족하는 최대 길이를 찾아나가면 완성입니다.

 

 

코드 

---

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long n,k;
long long arr[1000001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin>>n>>k;
    long long total=0;
    for(int i=0;i<n;i++) cin>>arr[i];
    sort(arr,arr+n);
    long long high=arr[n-1];
    long long low=1;
    long long result=0;
    while(low<=high){
        long long mid=(high+low)/2;
        long long ans=0;
        for(int i=0;i<n;i++){
            ans+=(arr[i]/mid);
        }
        if(ans>=k){
            if(result<mid) result=mid;
            low=mid+1;
        }
        else if(ans<k) high=mid-1;
    }
    cout<<result<<"\n";
    return 0;
}

funny algorithms ^9^~