BOJ 2805 나무 자르기

이 문제는 얼마전 포스팅했던 BOJ 1654 랜선 자르기 문제와 100%일치하는 문제이다. 

핵심은 적절한 나무 길이를 구하기 위해 이진 탐색을 이용해야하는 것이다. 

https://devconf.tistory.com/65

BOJ 1654 랜선 자르기

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;

typedef long long ll;

int n, m;
vector<ll> len;
ll result;

bool cmp(ll a, ll b)
{
	return a > b;
}

void BS(ll l, ll r)
{
	if(l > r)
	{
		return;
	}

	ll mid = ceil((double)(l + r) / 2);
	ll total = 0;
	for(int i = 0; i < n; i++)
	{
		if(mid <= len[i])
		{
			total += (len[i] - mid);
		}
	}

	if(total < m)
	{
		BS(l, mid - 1);
	}
	else
	{
		result = max(result, mid);
		BS(mid + 1, r);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;

	for(int i = 0; i < n; i++)
	{
		ll num;
		cin >> num;
		len.push_back(num);
	}

	sort(len.begin(), len.end(), cmp);

	BS(0, len[0]);

	cout << result;
}