[백준 2805] 나무 자르기

나무 자르기

문제설명

나무의 수, 최소 필요한 나무의 길이, 그리고 각 나무의 길이를 입력 받는다.
그리고 톱의 최대 높이를 설정해서 필요한 나무의 길이를 구할 수 있게 되는 값을 구하자.

알고리즘

1. 값을 각각 입력 받는다. 이때 long long 타입으로 입력 받는다.
2. 나무의 각 길이를 입력 받은 벡터를 정렬하고, 이분 탐색을 하기위해 0부터 나무의 최대 값을 매개변수로 넣는다.
3. 이분 탐색 과정에서 나무를 잘랐을 때 얻을 수 있는 양을 구한다.
4. 얻을 수 있는 양이 최소 조건에 도달 할 수 있는지 확인하고 도달 할 수 있는 경우 max함수로 그 톱의 길이를 갱신한다.
5. 도달할 수 없는 경우는 end-1을 해서 범위를 좁혀준다.
6. 위의 과정을 반복해서 result 변수에 담긴 값을 출력한다.

---

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long N, M;
vector <long long> tree; 
long long  result;

void binary_search(long long start, long long end)
{
    while (start <= end)
    {
        long long mid = (start + end) / 2;
        long long sum = 0;

        for (int i = 0; i < N; i++)//얻을 수 있는 나무의 양 구하기
        {
            if (tree[i]- mid> 0)
                sum += tree[i]- mid;
        }
        if (sum >= M)//얻을 수 있는 나무양이 최소한의 양보다 크거나 같을 떄
        {
            result = max(result, mid);//답을 구할 때 최대를 구해야하므로 갱신
            start = mid + 1;//기준점을 좀 더 높여서 최소한의 H를 구함 
        }
        else//나무 양이 최소 보다 작을 때 -> 기준점을 낮춰야함  
        {
            end = mid - 1;
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N>>M;
    for (int i = 0; i < N; i++)//각 나무의 높이 저장
    {
        long long num;
        cin >> num;
        tree.push_back(num);
    }
    sort(tree.begin(), tree.end());//오름 차순 정렬 
    binary_search(0, tree.back());//최대값이랑 0 전달

    cout << result;
    return 0;
}

고찰

이번 문제는 전부 조회하면 그냥 풀 수 있는 단순한 문제이지만, 그렇게 풀면 시간초과가 발생한다. 따라서 이분탐색을 사용할 필요가 있다.
이분탐색 알고리즘을 사용하여 기준값을 정해주고 구해서 시간복잡도를 줄일 수 있다.