[Algorithm] Baekjoon 2805번 : 나무 자르기

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

2805번: 나무 자르기

int n = 0;
long long m = 0;
vector<long long> v;
 
 
void solution()
{
    sort(v.begin(), v.end());
    long long left = -1;
    long long right = 2000000001;
 
 
    while (left + 1 < right)
    {
        long long mid = (left + right) / 2;
        long long cutTreeHeight = 0;
 
        if (mid >= 0)
        {
            for (int i = 0; i < v.size(); ++i)
            {
                if (v[i] > mid) // 자를 수 있으면
                {
                    cutTreeHeight += v[i] - mid;
                }
            }
        }
 
        if (cutTreeHeight < m) // 더 잘라야 되면
        {
            right = mid; // 더 자르려면 h값이 낮아져야됨. 그래서 영역을 왼쪽으로 이동.
        }
        else
        {
            left = mid; // 영역을 오른쪽으로
        }
    }
 
    cout << left;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
 
    long long temp;
 
    cin >> n >> m;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> temp;
 
        v.push_back(temp);
    }
    
    solution();
}

이전 문제에 이어서 좀 더 확실하게 머리속에 인지하려고 푼 이분탐색문제.

 

일단 각 절단기 높이마다 자를 수 있는 나무를 구할 수 있다.

그러면 우리가 구해야할 것은, 요구되는 나무길이를 만족하는 최대의 절단기 h값이다.

 

예를 들어서 요구되는 나무길이가 7이라 치자.

절단기높이가 4일 때 나무길이를 6만큼 얻을 수 있고, 절단기 높이가 5일 때 나무길이를 8만큼 얻을 수 있다고 가정한다.

그러면 여기서 정답은 5이다. 즉, 조건을 만족할 때(자를 나무길이 >= 요구되는 나무길이) 최대의 h값을 구하는 것이다.

 

이걸 인지하고 범위를 계속 좁혀나가면 된다. 참고로 0도 범위에 넣어야한다는걸 잊지말자.