[백준]2805_나무 자르기

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

Solved

✔ 알고리즘 분류: 이분 탐색
✔ 나무 절단기는 주어진 나무들을 지정한 높이대로 다 자른다. 그러니 우리가 얻을 수 있는 나무의 길이는 h높이의 나무에서 v 높이만큼 자를 때 (h-v)만큼이다.
✔ 적어도 M미터의 나무를 집으로 가져가기 위해 절단기에 설정할 높이의 최댓값을 구하자.
✔ 이분 탐색: 정렬되어 있는 리스트에서 어떤 값을 빠르게 찾는 알고리즘. 리스트의 크기가 N일 때 O(logN)의 시간이 걸린다.
✔ 이 문제에 이분 탐색을 적용한다면: v만큼 잘랐을 때 자른 나무들의 길이의 합이 필요한 나무의 길이 m이 되는 v를 찾자.
1. 이분 탐색하여 v 후보 하나를 구한다.
2. 그 v 후보만큼 나무를 자른다면 총 얼마의 나무를 얻을 수 있는 지 구한다.
3. 구할 수 있는 나무의 길이가 m과 같다면 정답을 출력하고 종료한다.

using namespace std;
#include <iostream>
#define MAX 1000000

long long n, m;
long long trees[MAX];
long long maxV = -1;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> trees[i];
		maxV = max(maxV, trees[i]);
	}
	long long left = 0, right = maxV;
	long long answer = 0;
	while (left <= right) {
		long long mid = (left + right) / 2; //자르는 높이
		long long sum = 0;
		for (int i = 0; i < n; i++)
			if (mid < trees[i])
				sum += (trees[i] - mid);
		if (sum >= m) {
			if (mid > answer)
				answer = mid;
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	cout << answer << '\n';
	return 0;
}