cpp) 백준 2805: 나무 자르기

Problem

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

2805번: 나무 자르기

 
적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하시오.
 
 

Solution

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n, m;  // 나무의 수, 집에 가져갈 나무 길이
vector<int> tree;  // 한 줄에 연속해있는 나무 높이

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

    cin >> n >> m;

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

    int start = 0;
    int end = *max_element(tree.begin(), tree.end());  // 나무 높이 최댓값
    int result = 0;  // 정답값

    while(start<=end){
        long long int sum = 0;    // 나무 길이 합
        int mid = (start+end)/2;  // 절단기 높이
            for(int i=0;i<n;i++){
                if(tree[i]>mid)
                    sum += tree[i]-mid;
            }
            if(sum<m){
                // 절단된 나무 길이가 원하는 나무 길이 미만
                end=mid-1;
            } else {
                // 절단된 나무 길이가 원하는 나무 길이 이상
                result = mid;
                start=mid+1;
            }
        }

    cout << result << '\n';
    
    return 0;
}

이 문제는 이분탐색을 이용하면 빠르게 정답을 구할 수 있다. 먼저 start는 0, end는 나무 길이의 최댓값, mid는 start와 end의 중간값으로 설정한다. 한 줄에 놓인 나무들이 mid 값 이상이면 자를 수 있게 되므로 나무 길이의 합인 sum 값을 구할 수 있다.
 
sum 값이 m(원하는 나무 길이) 미만이면, 조건을 만족하지 못하기 때문에 절단기 높이를 내려줘야 한다.
 
sum 값이 m 이상(원하는 나무 길이)이면, 조건을 만족하기 때문에 정답값으로 설정해줄 수 있다. 하지만 문제에서는 최적의 값을 구해야 하기 때문에 반복문이 끝날 때까지 조건을 만족하는 범위에서 절단기 높이를 올려줘야 한다. 
 
(주의할 점! ‘적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 것’이므로 sum 값과 m 값이 같을 필요는 없다.)
 
 

Reference

https://tooo1.tistory.com/123

[백준(BOJ)] 2805번 : 나무 자르기 - C++[CPP]

https://notepad96.tistory.com/40

C++ Vector 최대값, 최소값, 인덱스 구하기