백준 2805 나무자르기 [Binary_Search 알고리즘]

문제 설명

 

---

 

풀이 과정

 

1. 어떠한 값을 특정 범위 안에서 탐색하면서 최대, 최소값을 구하는 문제이므로 이분탐색을 생각함. 

 

2. left , right를 설정하고 mid가 최종 내가 잘라야하는 나무 높이로 설정하여 문제를 해결. 

 

헷갈렸던 부분.

 

- mid 값의 갱신 위치가 left , right보다 위에 있게 된다면 해당 값의 결과 반영이 while 조건문에 들어갈때 반영이 안되므로

  1칸씩 밀리게 된다 따라서  mid값의 초기화는 left와 right의 결과값에 따라 반영해야 하고 아니면 answer 로 right 값을 내보내야 한다. 

---

코드

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

using namespace std; 

bool Cut_Tree_Result(vector<int>& _vecTree, int cut_height, int _TargetTotalHeight)
{
	long long Cut_Result = 0;

	for(auto& iter : _vecTree)
	{
		if (iter <= cut_height)
			continue;

		else
			Cut_Result += (iter - cut_height);
	}

	if (_TargetTotalHeight > Cut_Result)
	{
		return true; // 나무가 더 필요한 경우 높이를 낮춰서 잘라야함
	}

	else
		return false;  // 나무가 목표량 보다 높다면 높이를 더 높게해서 잘라야함.

}


int main()
{
	int N, M = 0; 
	vector<int> m_vecTree; 

	cin >> N >> M; 

	for(int i=0; i<N; i++)
	{
		int input_Num = 0; 
		cin >> input_Num; 
		
		m_vecTree.push_back(input_Num);
	}

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

	int left  = 1;
	int right = 1000000000;
	int mid = (left + right) / 2;
	
	while(left <= right)
	{
		if(Cut_Tree_Result(m_vecTree, mid,M))
		{
			right = mid - 1;
		}

		else
		{
			left = mid + 1; 
		}

		mid = (left + right) / 2;
	}

	
	cout << mid;

	return 0; 
}