BOJ 2805 - 나무 자르기 / C++

문제 링크 : https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

 

문제 풀이

나무들의 높이가 주어지고 절단기의 길이가 x일 때 (trees[i] - x)만큼 집에 나무를 가져갈 수 있다.

적어도 m미터의 나무를 가져가기 위한 절단기의 최대 길이를 구하면 된다.

이를 구하기 위해 이분 탐색을 이용한다.

 

일반적인 이분 탐색은 원소 값들을 탐색하지만 해당 문제에서는 원소 값들을 탐색해서는 답을 찾을 수 없다.

따라서 0부터 나무의 최대 높이를 이분 탐색하여 절단기의 길이를 임의로 정하고 잘린 나무의 합을 구한 뒤 최댓값 최솟값을 변경해나가며 답을 탐색한다.

 

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n, m; //나무의 수 n, 집으로 가져가려는 나무의 길이 m
    vector<int> trees;

    cin >> n >> m;

    for(int i=0; i<n; i++){
        int tmp;
        cin >> tmp;
        trees.push_back(tmp);
    }

    sort(trees.begin(), trees.end());

    int l = 0, r = trees[n-1];
    int ans;

    while(l <= r) {
        int mid = (l + r) / 2;
        long long sum = 0;

        for(int i=0; i<n; i++){
            if(trees[i] > mid) {
                sum += (trees[i] - mid);
            }
        }

        if(sum >= m) {
            ans = mid;
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }

    cout << ans;
}