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

문제 링크

2805번: 나무 자르기

---

 

---

이분 탐색 문제다.

 

간단하게 나무를 자르는 값을 left = 1, right = 가장 긴 나무의 길이로 해서 이분 탐색을 이용해 값을 구하면 된다.

 

이분 탐색을 해서 나무를 자르는 값으로

나무를 잘랐을 때 잘려나간 나무의 값이 현재 필요한 나무의 값과 같으면 값을 출력하면 된다.

---

주의할 점은

이 부분인데, 만약 같은 경우가 없을 경우에 나오면 계산된 값이 현재 필요한 나무의 값보다 작으면

나무를 자르는 길이값을 -1하면 된다. ( 이분 탐색상 )

 

 

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

const int maxWoodCnt = 1000001;
long long woods[maxWoodCnt];

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

	long long maxWoodLength = 0;
	long long woodCnt, woodLength;
	cin >> woodCnt >> woodLength;

	for (int i = 0; i < woodCnt; ++i)	// 입력 받기
	{
		cin >> woods[i];
	}
	sort(woods, woods + woodCnt);

	long long left = 1, right = woods[woodCnt-1], mid = 0, calcN = 0;
	while (left <= right)
	{
		mid = (left + right) / 2;
		//계산
		calcN = 0;
		for (auto len : woods)
		{
			if (len - mid > 0)
				calcN += len - mid;
		}

		if (calcN == woodLength)
			break;
		else if (calcN < woodLength)	// 값이 더 커져야 한다
			right = mid - 1;
		else
			left = mid + 1;
	}

	if (calcN < woodLength)
	{
		cout << mid - 1;
		return 0;
	}

	cout << mid;

}