(매일 BOJ) C++ 2805번 나무 자르기

이번 문제는 2805번 나무 자르기 이다.

접근법

이 문제는 이분 탐색을 사용해서 가장 높이 자를 수 있는 지점을 찾아내는 문제이다. 이분 탐색과 관련된 자세한 설명을 보고 싶으면 아래 글을 참고할 수 있다.

2025.07.25 - [매일 BOJ] - (매일 BOJ) C++ 2512번 예산

(매일 BOJ) C++ 2512번 예산

 

작성코드

# include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);
    int N,M; // N 나무의 수 / M 가져갈 나무의 길이
    cin >> N >> M;
    vector<int> v; // 각 나무의 높이 배열
    for (int i = 0; i < N; i++) // 각 나무의 높이 input
    {
        int hight;
        cin >> hight;
        v.push_back(hight);
    }

    sort(v.begin(),v.end()); // 이분탐색용 정렬
    int start = 0;
    int end = v.back();
    int result = 0;

    while (start <= end){
        int mid = (start + end) / 2;
        long long sum = 0;
        for (int i = 0; i < v.size(); i++){
            if (v[i] > mid) sum += (v[i] - mid);
        }

        if (M <= sum) {
            if(mid <= end) result = mid;
            start = mid + 1; // sum 값이 더 크다면 더 높이 자를 수 있음 > start 값 증가
        }
        else{
            end = mid - 1; // sum  값이 더 작으면 mid 보다 작은 범위에서 탐색
        }


    }
    cout << result;


}