[백준] 2805번 나무 자르기

문제 링크

 

풀이

내가 가져갈 수 있는 나무 길이가 나오는, 나무의 절단 높이를 구하는 문제다. 20 높이의 나무의 15로 높이로 절단하면 5를 가져간다. 이 문제의 특성은 이분 탐색을 통해 절단 높이를 구해가는 과정에서, 절단 높이가 작아질수록 잘린 나무의 길이가 커지는 데 있다. 그러므로 일반적인 이분 탐색에서 high, low를 구하는 조건을 반대로 해주면 된다.

 

코드

#include <cstdio>
#include <vector>
using namespace std;

// 2805번
int main()
{	
	int N; // 나무 수
	scanf("%d", &N);

	vector<long long> trees(N);
	long long M;		  // 필요한 나무의 길이
	long long answer = 0; // 절단기에 설정할 최대 높이
	long long high = 0, low = 1;
	scanf("%lld", &M);

	for (int i = 0; i < N; ++i)
	{
		scanf("%lld", &trees[i]);
		high = high < trees[i] ? trees[i] : high;
	}
	while (low <= high)
	{
		long long mid = (high + low) / 2;
		long long sum = 0;
		for (int i = 0; i < N; ++i)
		{
			auto cut_reulst = trees[i] - mid;
			if (cut_reulst <= 0) continue;
			sum += cut_reulst;
		}
		if (M <= sum)
		{
			answer = mid;
			low = mid + 1;
		}
		else
			high = mid - 1;
	}
	printf("%lld\n", answer);
}