BOJ(백준) 2805 - 나무 자르기

두 가지 접근법을 사용 할 수 있다. 이분 탐색 정렬과 그리디 알고리즘 먼저 이분탐색을 생각해보자.

절단기 높이는 H는 0과 가장 큰 나무의 높이 사이의 값이 된다. 그럼 이를 이분탐색으로 조정할 수 있지 않을까?

이분탐색의 매 루프마다 얻은 middle 값으로 산정한 자른 나무의 길이 총합이 M보다 작으면 H는 그보다 작다는 뜻이고, 크면 H는 그 이상이라는 뜻이다. 사실 이 풀이법은 많이 서술되어 있으니 이정도만 설명하고 넘기겠다.

#include #include int main() { size_t N, M; size_t* tree_arr = nullptr; size_t min_height = 0; size_t max_height = 0; size_t height; std::cin >> N >> M; tree_arr = new size_t[N]; for (size_t i = 0; i < N; i++) { std::cin >> tree_ar...