[BOJ] 2805번 나무 자르기

문제 바로가기

접근

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

먼저 0부터 나무의 최대 높이까지 이분 탐색을 한다. 그리고 중간값으로 나무들을 잘랐을 때 잘리는 나무들의 길이를 모두 합한다. 이 합이 상근이가 구하는 나무의 길이보다 크거나 같다면, 나무를 가져갈 수 있다. 다만, '높이의 최댓값'을 구해서 잘리는 나무들을 최소화해야 한다.

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

#define MAX 1000000

int N, M;
long long tree[MAX] = {0};
long long result = 0;

long long bsearch(int low, int high) {
  long long sum = 0;
  long long mid = (low  + high) / 2;

  if(low > high)
    return result;

  for(int i = 0; i < N; i++) {
    if(tree[i] < mid)
      break;
    sum += tree[i] - mid;
  }

  if(sum >= M)
    result = result < mid ? mid : result;

  if(sum > M)
    return bsearch(mid + 1, high);
  else
    return bsearch(low, mid - 1);
}

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

  cin >> N >> M;
  for(int i = 0; i < N; i++)
    cin >> tree[i];
  sort(tree, tree + N, greater<int>());
  cout << bsearch(0, tree[0]);
}