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

문제 링크

설명

나무들을 mid만큼씩 잘랐는데 목표치보다 많이 잘랐으면 mid를 높여야 때문에 start를 조정하고,
반대로 목표치보다 적게 잘랐으면 end를 조정해서 mid를 낮춘다.

제출 코드

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<long long> arr;

bool Check(long long height)
{
	long long result = 0;

	// 배열을 돌면서 싹 다 커팅
	for (int i = 0; i < n; i++)
	{
		if(arr[i] >= height)
			result += arr[i] - height;
	}

	if (m > result)
		return false;
	else
		return true;
}

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

	cin >> n >> m;

	long long max = 0;

	for (int i = 0; i < n; i++)
	{
		long long n;
		cin >> n;
		arr.push_back(n);
		if (max < arr[i])
			max = arr[i];
	}

	long long start = 0, end = max;

	while (start+1 < end)
	{
		long long mid = start + ((end - start) / 2);

		if (Check(mid))
			start = mid;
		else
			end = mid;
	}

	cout << start;

	return 0;
}