[백준/c++] 2805 나무 자르기

 

 

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

2805번: 나무 자르기

 

✨ 문제 풀이

이분탐색은 항상 그렇듯이 무엇을 기준으로 잡고서 탐색할 것인지가 중요하다.

최소 M미터의 나무 토막을 가져갈 때 절단기 높이의 최댓값을 구해야하므로 절단기의 높이를 기준으로 잡고 탐색한다.

그렇다면 탐색할 첫 기준이 중요한데, 절단기가 모든 나무를 자르는 경우인 0을 start로, 아무것도 자르지 않는 최대 높이인 가장 큰 나무의 길이를 end로 설정한다. 그리고 절단기 높이를 mid로 조정해가며 탐색한다.

 

절단기의 높이가 커지면 자르는 나무 토막의 길이가 작아진다. 반대로 절단기 높이가 작아지면 자르는 나무 토막의 길이가 커진다.

여기서 우리는 절단기 높이를 mid로 했을 때, 총 자른 나무 토막의 길이(tree - mid)의 합이 몇인지 계산하고 이 총 길이가 m보다 큰지를 계속해서 비교해야 한다. 이때 총 길이를 sum이라고 한다. 만약에 이 sum 값이 m보다 크다면 절단기 높이를 더 높일 수 있으므로 start값을 mid+1로 조절하고, 만약 m보다 작다면 절단기 높이를 더 낮춰야 하므로 end값을 mid-1로 조절한다.

 

여기서 가장 주의해야할 부분은 바로 조건의 숫자 범위이다.

나무의 최대 개수는 1,000,000, 상근이가 가져가고 싶은 나무 길이 총합의 최댓값은 2,000,000,000 이고 각각의 나무의 높이의 최댓값은 1,000,000,000 이다.

나무의 개수가 1,000,000, 모든 나무의 높이가 1,000,000,000인 경우를 생각해보자. 처음 start 값인 0, 즉 절단기의 높이를 0으로 선정했다고 했을 때, 상근이가 얻을 수 있는 나무 토막의 길이는 1,000,000 * 1,000,000,000 = 1,000,000,000,000,000 이므로 unsinged int의 벙위인 4,294,967,295를 훌쩍 뛰어 넘는다. 따라서 양수를 최대 9,223,372,036,854,775,807 까지 지원해주는 long long값으로 절단기의 높이의 범위를 설정해야 한다.

 

🗓 코드

#include <iostream>
using namespace std;
#define MAXTREE 1000001

int n, m;
long long start = 0, end = 0, mid;

int trees[MAXTREE];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> trees[i];
        if (trees[i] > end)
            end = trees[i];
    }

    long long sum, answer = 0;
    while (start <= end)
    {
        mid = (start + end) / 2;
        sum = 0;
        for (int i = 0; i < n; i++)
            if (trees[i] > mid)
                sum += trees[i] - mid;

        if (sum >= m)
        {
            start = mid + 1;
            if (answer < mid)
                answer = mid;
        }
        else
            end = mid - 1;
    }
    cout << answer << '\n';
}