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

---

문제

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

2805번: 나무 자르기

---

발상

나무를 가장 적게 자르면서 환경을 위해 최소한의 나무 길이를 보장해야 하므로 이분 탐색을 사용하여 

min값은 0, max값은 나무의 최대길이로 정해, 나무길이를 벡터안에 넣고, 포문을 돌리면서 해당 높이를 잘랐을 때, 얻을 수 있는 나무의 길이를 비교해보고 적으면 min을 올리고, 많으면 max를 내리는 방식으로 진행했다.

---

소스코드

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

using namespace std;

int main()
{
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	vector <long long>v;
	long long repeat, need,input,answer = 0;
	cin >> repeat >> need;
	for (int i = 0; i < repeat; i++)
	{
		cin >> input;
		v.push_back(input);
	}
	sort(v.begin(), v.end());
	long long low = 0, high = v.back(), middle;
	while (low <= high)
	{
		long long temp = 0;
		middle = (low + high) / 2;
		for (auto i : v)
			if (i > middle)
				temp += i - middle;

		if (temp >= need)
		{
			answer = middle;
			low = middle + 1;
		}
		else
		{
			high = middle - 1;
		}
	}
	cout << answer;
}