[백준/C++] 2805번 나무 자르기

2805번: 나무 자르기

풀이

절단기 높이보다 큰 나무들만 잘릴 때, 적어도 M미터만 자르기 위한 절단기 설정 높이의 최대값을 구하는 문제이다.

이분 탐색으로 절단기 설정 높이를 찾는다. mid값이 절단기 높이이며 범위는 1~나무 중 최대 높이이다. 나무의 높이가 절단기 설정 높이보다 클 때 나무가 베어진다. 이때 베어진 나무 길이의 합을 구해 M미터 보다 크거나 같은 경우 절단기의 높이를 높여야 하므로 mid의 오른쪽 범위를 탐색하기 위해 left를 옮긴다. 반대로 베어진 나무 길이의 합이 M미터 미만일 경우 절단기의 높이를 낮춰야 하므로 right를 옮겨 mid의 왼쪽 범위를 탐색한다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std
int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  vector<long long int> v(1000001);
  long long int N, M, result = 0;
  cin >> N >> M;

  for (int i = 0; i < N; i++)
    cin >> v[i];

  long long int left = 1, right = *max_element(v.begin(), v.end());
  while (left <= right)
  {
    long long int mid = (left + right) / 2, sum = 0;

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

    if (sum >= M)
    {
      left = mid + 1;
      result = max(result, mid);
    }
    else
      right = mid - 1;
  }
  cout << result;
  return 0;
}