[백준] 2805번 : 나무 자르기

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

문제

알고리즘 접근 방법

• 절단기에 설정한 높이가 정해지면
  나무의 양을 계산하는 데에 소비되는 시간 복잡도 = O(N)

• 절단기에 설정할 높이를 탐색하는 시간복잡도
  1 ~ 십억을 탐색
  절단기에 설정할 높이가 낮으면 낮을수록 잘려질 나무의 양이 많아짐.
  이분 탐색을 이용한다. (O(log높이의 범위)) = 30

자를 수 있는 범위 : 0~나무의 높이 중 최대값

이분탐색 경계 설정 주의하기

풀이

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

// 나무 자르기
using namespace std;

vector<int> tree;
long long N, M, H; // 나무의 수 N, 상근이가 집으로 가져가려고 하는 나무의 길이 M, 나무 높이 H


long long cut(int k){
    long long sum = 0;
    for(int i=0; i<N; i++){
        if(tree[i] > k) sum += tree[i] - k;
    }
    return sum;
}


int main(){

    cin >> N >> M;

    for (int i=0; i<N; i++){
        cin >> H;
        tree.push_back(H);
    }
    
    // 나무 자르기
    int low = 0, high =*max_element(tree.begin(),tree.end()), mid = (low+high)/2; H;
    long long wood = 0;

    // 이분탐색으로 잘라야 할 최대 나무 길이 찾기
    while(low<=high){
        mid = (low+high)/2,
        wood = cut(mid);
        
        if (wood < M) high = mid-1; // 나무 길이 높이기
        else { // 나무 길이 낮추기
            H = mid;
            low = mid+1;
        }; 
    }
    
    cout << H << '\n';
   
    return 0;
}

정리

와..너무 어렵게 생각했다
그냥 0~나무 최댓값이랑 이분탐색 하면 되는건데!!!!!

💡 참고 포스팅

퉁이리님 블로그