백준 2805 나무 자르기(c++)

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

2805번: 나무 자르기

<코드>

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

int main()
{
	int n,m;
	cin>>n>>m;
	vector<int>tree;
	for(int i=0;i<n;i++)
	{
		int a;
		cin>>a;
		tree.push_back(a);
	}
	
	int l = 0;
	int r = *max_element(tree.begin(),tree.end());
	int ans;
	int mid;
	while(l<=r)
	{
		long long sum=0;
		mid = (l+r)/2;
		for(int i=0;i<n;i++)
		{
			if(tree[i]>mid){
				sum += (tree[i]-mid);
			}
		}
		if(sum<m)
		{
			r = mid -1;
		}
		else
		{
			ans = mid;
			l = mid +1;
		}
	}
	cout<<ans;
	
}

<풀이과정>

이 문제는 이분 탐색(binary_search)로 풀 수 있다. left = 가장 작은 원소(tree[0])부터 right = 가장 마지막 원소(tree[n-1])를 합한 것의 절반부터 검사를 시작한다. (중간 원소부터 검사를 시작)

조건이 충족되면 구하고자 하는 나무길이의 최댓값은 mid값이 되고, while문(left<=right)가 만족할 때 까지 검사를 계속 한다. 그러다가 left가 right보다 커지는 순간이 오면 검사를 종료하게 되면서 while문을 종료하게 된다.

예시) n, m  = 4, 7 

나무의 높이 20 15 10 17인 경우

중간 값(20+10)/2 = 15부터 검사를 시작하며  15인 경우는 sum = (20-15)+(17-15) = 7로써 sum = m이 같은 상황이 된다.

그리고 l이 16이 되고 중간값(16+20)/2 = 18을 검사하면 sum = (20-18)=2가 되면서 if(sum<m)을 만족시키기에 r=mid-1=19이 된다.

반복해서 계산하면 (18+19)/2 = 18이 되므로 sum = (20-18)=2가 되고 if(sum<m)을 만족시키기에 r=mid-1=18이 됨과 더불어 l과 r이 같아지는 상황이 오게 된다.

다음부분에서 while문을 종료하게 되며 ans을 반환한다.