[백준(BOJ)/2805] 나무 자르기 C++

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

2805번: 나무 자르기

---

풀이

나무의 수, 나무의 길이의 최대값이 크기 때문에 높이를 탐색할 때 brute force 알고리즘을 쓴다면, 시간 초과가 될 수 있다. 이 경우 시간복잡도가 O(logN)인 Binary Search 알고리즘을 사용한다. 

 

Binary Search 알고리즘을 사용하려면 정렬된 데이터의 경우에 사용이 가능하다.

Binary Search 알고리즘을 쓰기 위해서는 배열로 나무의 길이들을 입력 받은 후, 정렬을 해 주어야 한다.

 

아래 코드에서 mid는 절단기에 설정한 높이 H이다. 

H가 클수록 잘려나가는 나무의 길이는 작아진다.

따라서 얻어낸 나무의 길이 get_trees의 값이 큰 경우, H가 현재의 mid 값보다 커져야 값을 줄일 수 있다. 

---

 

코드

 

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    long long N, M;
    cin >> N >> M;
    
    long get_trees, max_height;
    long long trees[N];
    for(long long i = 0; i < N; i++) cin >> trees[i];
    
    sort(trees, trees+N); // binary search => sorting 필요
    long long start = 0;
    long long end = trees[N-1];
    
    // binary search
    while(start <= end) {
        long long mid = (start + end) / 2;
        get_trees = 0;
        
        for(long long i = 0; i < N; i++)
            if(trees[i] > mid) get_trees += trees[i] - mid;
        
        if(get_trees == M) { 
            max_height = mid;
            break;
        }
        else if(get_trees > M) { // height를 높여야 잘라서 얻는 나무 길이 감소
            start = mid + 1;
            max_height = mid;
        }
        else end = mid - 1; // height를 낮춰야 얻는 나무 길이 증가
    }
    cout << max_height;
}