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

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

간단하게 생각해서 맨 위에서부터 잘라나가면 정답을 찾을 수 있지 않을까? 지만

N, M의 범위가 굉장히 크기 때문에 시간 초과가 발생할 것이다.

 

그렇기 때문에 이분 탐색을 활용해 문제를 풀어야 한다.

---

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

using namespace std;

int N, M;
vector<int> list;

int solve()
{
	int answer = 0;
	int minValue = 0;
	int maxValue = list[N - 1];

	while (minValue <= maxValue)
	{
		long long int sum = 0;

		int midValue = (minValue + maxValue) / 2;

		for (int i = 0; i < list.size(); i++)
		{
			if (list[i] > midValue)
				sum += list[i] - midValue;
		}

		if (sum > M)
		{
			minValue = midValue + 1;
			answer = midValue;
		}	
		else if (sum < M)
			maxValue = midValue - 1;
		else
		{
			answer = midValue;
			break;
		}	
	}

	return answer;
}

int main()
{
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		int temp;
		cin >> temp;

		list.push_back(temp);
	}

	sort(list.begin(), list.end());

	cout << solve() << endl;

	return 0;
}

 

나무 중 작은 나무(minValue)와 큰 나무 (maxValue)의 중간값(midValue)를 활용하여 sum을 구한다.

 

그 값이 주어진 M보다 작을 경우, 나무가 아직 부족하기 때문에 max값을 낮추어 절단기의 최대 높이를 줄이게 된다.

M보다 높을 경우, 나무가 충분해졌기 때문에 최댓값을 구하기 위해 min값을 높여 절단기의 최대 높이를 올리게 된다.

 

이 때, 주의해야할 점은 M값과 딱 맞추는 경우도 있지만 무조건 크게 가져가야 할 경우가 있다는 점이다.

그렇기 때문에 M보다 높거나 같을 때, answer의 값을 midValue로 설정해주는 것이 필요하다.