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

문제

2805번: 나무 자르기 (acmicpc.net)

2805번: 나무 자르기

코드

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

using namespace std;

int n, m, mx;
vector<int> v;

void input() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  mx = -1;
  cin >> n >> m;
  v = vector<int>(n);
  for (int &i: v) {
    cin >> i;
    if (i > mx) mx = i;
  }
}

long long int cutTree(int height) {
  long long int tree = 0;
  for (int i: v) {
    if (i <= height) continue;
    tree += i - height;
  }
  return tree;
}

int binarySearch() {
  int res = -1;
  int low = 0;
  int high = mx;
  while (low <= high) {
    int mid = (low + high) / 2;
    long long int tree = cutTree(mid);
    if (tree == m) return mid;
    if (tree > m) {
      res = mid;
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return res;
}

int main() {
  input();
  cout << binarySearch();
  return 0;
}

 

설명

절단기에 설정한 높이가 높을수록 가져갈 수 있는 나무의 길이가 짧아지고,
높이가 낮을수록 가져갈 수 있는 나무의 길이가 길어진다.
즉, 설정한 높이와 잘린 나무의 길이는 음의 상관관계가 있으므로 이분탐색을 할 수 있다.