백준 1654번 : 랜선 자르기 (C++) (이분탐색)

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

1654번: 랜선 자르기

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    int k,n;
    cin>>k>>n;
    vector<long long> arr;
    int t;
    for(int i=0;i<k;i++)
    {
        cin>>t;
        arr.push_back(t);
    }
    long long max=*max_element(arr.begin(),arr.end());
    long long min=1;
    long long mid;
    long long ans=0;
    while(min<=max)
    {
        mid=(min+max)/2;
        long long sum=0;
        for(int i=0;i<k;i++)
        {
            sum+=arr[i]/mid;
        }
        if(sum<n) max=mid-1;
        else
        {
            if(ans<mid)ans=mid;
            min=mid+1;
        }
    }
    cout<<ans;
    return 0;
}

 

풀이

 k와 n 값이 주어지고 k개의 랜선의 길이가 주어질 때 k개의 랜선을 n개의 랜선으로 잘라서 만들 수 있는 가장 긴 길이를 구하는 문제이다. (각 랜선을 자르고 남은 부분은 버려진다)

 

랜선들을 가장 짧게 자르는 길이는 1cm이다. k=3, n=10이고 각각의 랜선들의 길이가 3cm, 3cm, 4cm인 경우에 각각의 길이를 1cm로 만들어야 한다. 가장 길게 자르는 길이는 주어진 랜선들 중 가장 긴 길이이다. k=3, n=3이고 각각 300cm, 300cm, 300cm인 경우 각각의 길이를 300cm로 만들어야 한다. 랜선의 길이는 2^31-1보다 작거나 같은 자연수로 주어진다. 2^31-1은 2,147,483,647 이기 때문에 가장 짧은 길이인 1부터 가장 긴 길이인 2^31-1까지의 모든 값을 검사해서 가장 길게 자를 수 있는 값을 찾는 O(n) 방식은 문제의 제한 시간인 2초를 쉽게 넘기게 될 거라고 생각해서 O(log2n) 의 시간복잡도를 가지고 있는 이분 탐색을 사용했다.

코드는 벡터에 k개의 랜선의 길이를 각각 입력받는다. 그 뒤에 max_element() 함수를 사용해서 가장 긴 랜선의 길이를 max 변수에 준다. 그 뒤에 이분 탐색을 수행하면서 mid 값으로 랜선들을 잘랐을 때 n개보다 작은 값이 나온다면 더 작은 mid 값으로 잘라야 하므로 max=mid-1을 해준다. 랜선들을 잘랐을 때 n개보다 많은 값이 나온다면 그럴 때 가장 큰 mid 값을 저장하기 위해 31행을 수행하고 더 크게 잘라도 n개보다 많은 값이 나오는지 알아보기 위해 32행에서 min=mid+1을 수행해준다. 이를 min<=max가 true일 때까지 수행한 뒤 ans의 값이 답이다.