[이분 탐색] 백준 2805: 나무 자르기

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

 

이분 탐색의 기본을 사용하는 문제이다.

 

먼저, 절단기 높이의 최소값은 0이고, 최대값은 나무들 중 가장 높은 나무의 높이이다. 따라서 초기에 min = 0, max = max(tree) 라고 하자.

 

우리가 구해야 할 것은 "원하는 만큼 나무를 가져갈 수 있는 절단기의 최대 높이" 이다. 따라서 절단기 높이에 따라 구할 수 있는 나무의 양이 요구치보다 적을 때는 절대 정답이 될 수 없되 절단기를 더 낮추어야 하므로, max = mid-1로 설정하고 다시 이분탐색을 진행한다.

 

반면 절단기 높이에 따라 구할 수 있는 나무의 양이 요구치보다 많을 때는 정답이 될 수 있되 절단기를 더 높여서도 해당하는 만큼의 나무를 구할 수 있는지 알아봐야 한다. 따라서 현재 절단기 높이를 일단 정답으로 저장하고, min = mid+1로 설정하여 다시 절단기 높이를 높여 본다.

 

int minHeight = 0;
    int maxHeight = 0;
    for(int i=0;i<treeNum;i++)
    {
        cin>>treeHeight;
        trees.push_back(treeHeight);
        maxHeight = max(treeHeight, maxHeight);
    }

    int answer = 0;

    while(minHeight<=maxHeight)
    {
        long long mid = (minHeight+maxHeight)/2;

        long long woods = calculateWood(trees, mid);

        if(woods<treeReq)
        {
            maxHeight = mid-1;
        }
        else if(woods>=treeReq)
        {
            answer = mid;
            minHeight = mid+1;
        }
    }

 

처음에 내가 틀렸던 이유는 long long type 대신 int type을 사용했기 때문이다. 

나무의 최대 길이가 1,000,000,000이고, 나무 요구량의 최대값이 2,000,000,000 이기 때문에 냉큼 int를 사용했었다. 그러나 "나무 요구량"이 아닌 "실제 채취한 나무량"은 int의 최대치를 넘길 수 있다는 것을 간과했다.

 

다음은 전체 코드이다.

#include <iostream>
#include <vector>

using namespace std;

long long calculateWood(vector<int> &trees, long long height)
{
    long long sum = 0;
    for(int i=0;i<trees.size();i++)
    {
        if(trees[i]>=height) sum+=(trees[i]-height);
    }
    return sum;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int treeNum, treeReq;

    cin>>treeNum>>treeReq;

    vector<int> trees;
    int treeHeight;
    int minHeight = 0;
    int maxHeight = 0;
    for(int i=0;i<treeNum;i++)
    {
        cin>>treeHeight;
        trees.push_back(treeHeight);
        maxHeight = max(treeHeight, maxHeight);
    }

    int answer = 0;

    while(minHeight<=maxHeight)
    {
        long long mid = (minHeight+maxHeight)/2;

        long long woods = calculateWood(trees, mid);

        if(woods<treeReq)
        {
            maxHeight = mid-1;
        }
        else if(woods>=treeReq)
        {
            answer = mid;
            minHeight = mid+1;
        }
    }

    cout<<answer;

}