백준 1624 랜선 자르기 ( binary_search)

문제

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory>
#include <climits>

using namespace std; 

bool possible(long long _mid, vector<int>& _vecLineBox, int _n)
{
    long long i_LineCount = 0; 

    for(auto& iter : _vecLineBox)
    {
        i_LineCount += iter / _mid;     
    }

    if (i_LineCount >= _n)
    {
        return true;  // start +1; 
    }
    else
        return false;  // end -1;

}



int main()
{
    //랜선을 모두 n개 같은 길이의 랜선으로 만들고 싶다.
    //ex) 300cm 렌선에서 140cm 자리 렌선을 두개 잘라내면 20cm는 버려야한다.  
    

    // 이 때 만들 수 있는 최대랜선의 길이 

    long long answer = 0;
    int K, N; 
    int i_inputLineLength = 0;
 
    vector<int> m_vecLineBox; 
   

    long long l, r; 
    
    cin >> K >> N;
    m_vecLineBox.reserve(K);

    for(int i=0; i<K; i++)
    {
        cin >> i_inputLineLength;
        m_vecLineBox.push_back(i_inputLineLength);
    }
    
    // N개를 만들어야함.
    sort(m_vecLineBox.begin(), m_vecLineBox.end()); 
    
    l = 1;  
    r = INT_MAX;    
 
    long long mid = (l + r) / 2;

    while(l <= r)
    {
        if (possible(mid, m_vecLineBox, N))
        {
            l = mid + 1;
        }

        else
            r = mid - 1;

        mid = (l + r) / 2;
    }

    answer = mid;

    cout << answer; 

    return 0;
}

 

 

 

 

문제 접근 순서.

 

1. 문제는 랜선의 N개로 나눌 수 있으며 그 중 최대의 길이를 원함

 

2. 랜선 길이의 범위를 구해야 하고 시간제한이 2초기 때문에 1초에 약 10*8 계산할 수 있는걸 감안해서 브루탈 포스 알고리즘

    으로는 시간 제약이 있음. 

 

3.  따라서 오름차순으로 랜선의 길이를 정렬할 수 있으며 범위는 랜선의 최소 길이 1 , 최대 길이 INX_MAX를 이용하면 

    이진 탐색(binary_search) 알고리즘으로 해결할 수 있다고 생각함. 

 

4.  해당 방법으로 진행하면서 구했다고 하더라도 바로 랜선의 최대 길이가 아닐 수 있으므로 start 지점을 '1' 만큼 계속 전진

     하면서 조건에 부합하는지 체크하며 답을 구함.