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

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

2805번: 나무 자르기

 

n개의 나무 중 m개 이상을 가져갈 수 있는 최소 높이를 구하는 문제입니다.

이분 탐색을 이용한 풀이와 높이를 비교하며 푸는 방법 두 가지가 있습니다.

 

먼저 이분 탐색을 사용한 일반적인 풀이입니다.

(이분 탐색이 left <= right,  left < right 등과 같이 여러 변형이 있고 쓰이는 곳이 달라집니다.

이건 종이에 써가면서 해보는게 좋을거 같네요!)

 

#include <iostream>
#include <algorithm>

using namespace std;

int input[1000000];

int BinarySearch(int n, int m)
{
	int left = 0;
	int right = 1000000000;

	while (left <= right)
	{
		int mid = (left + right) / 2;
		long long sum = 0LL;

		for (int i = 0; i < n; ++i)
		{
			if (input[i] > mid)
			{
				sum += (long long)input[i] - (long long)mid;
			}
		}

		if (sum == m)
		{
			return mid;
		}
		else if (sum > m)
		{
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
	}

	return right;
}

int main()
{
	int n, m;
	int left = 0;
	int right = 0;

	cin.tie(0);
	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		cin >> input[i];
	}

	sort(input, input + n);

	cout << BinarySearch(n, m) << endl;
}

 

다른 방법은 높이를 큰 순서로 나열한 후 잘라가며 원하는 수량을 체크하는 것입니다.

이 방법은 제가 알아낸 것은 아니고 어떤 분의 풀이였던 것 같습니다.

1

 

 

2

 

#include <iostream>
#include <algorithm>

using namespace std;

int input[1000001];

bool compare(int a, int b)
{
	return a > b;
}

int main()
{
	int n, m;
	long long sum = 0;
	int index = 1;
	int cut = 0;

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		cin >> input[i];
	}

	sort(input, input + n, compare);

	while (sum < m)
	{
		sum += ( (long long)input[index - 1] - (long long)input[index] ) * index;
		index++;
	}

	cut = (sum - m) / (index - 1);
	cout << input[index - 1] + cut << endl;
}

cut을 구하는 것이 핵심인 코드입니다. ㅎㅎ

(이때 index가 배열의 크기를 넘어서지 않기위해 n + 1개 만큼의 배열로 선언해주어야 합니당.)