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

 

알고리즘 분류: 이분 탐색, 매개 변수 탐색

문제 링크: https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

 

【 풀이 】

 

자를 수 있는 나무의 마지노선 길이를 구하는 문제이다.

이분 탐색으로 구하면 쉽게 해결할 수 있다.

start(최소 길이, 즉 0), end(최대 길이, 즉 배열에서의 최댓값) 두 변수를 이용해서 mid(중간값)를 설정하고

배열 요소에서 mid를 뺀 값을 모두 더한 값을 저장한다.

모두 더한 값이 m보다 크면 start를 mid+1로,

모두 더한 값이 m보다 작으면 end를 mid-1로 설정하고 반복문을 돌린다.

그렇게 end가 start보다 작거나 같아질 때까지 반복하면 우리가 원하는 값이 mid가 된다.

 

 

【 코드 】

 

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

vector<int>tree;
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int m, n;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		tree.push_back(num);
	}
	int start = 0;
	int end = *max_element(tree.begin(), tree.end());
	int height = 0;
	while (start <= end)
	{
		long long int sum = 0;
		int mid = (start + end) / 2;
		for (int i = 0; i < tree.size(); i++)
			if (tree[i] - mid > 0)
				sum += tree[i] - mid;
		if (sum < m)
			end = mid - 1;
		else
		{
			height = mid;
			start = mid + 1;
		}
	}
	cout << height;
	return 0;
}