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

 

문제 2805번

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

 

 

이 문제도 높이의 최댓값을 구하라는 것을 보니 이분탐색을 사용하면 되겠다.

 

벡터에 나무 길이를 모두 저장하고 start와 end를 이용하여 mid값을 정한다. mid는 높이를 나타낸다. 그래서 이 값보다 나무 길이가 더 크면 mid만큼 빼주고 total에 더해준다. 만약 그 total이 m보다 작다면 mid값을 줄여야하기 때문에 end를 mid-1위치로 옮긴다. 그 반대라면 result에 mid값을 저장해두고 start를 mid+1위치에 옮겨준다.

 

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<int> tree;

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int h;
		cin >> h;
		tree.push_back(h);
	}

	int start = 0, end = 1e9, result = 0;
	while (start <= end) {
		long long total = 0;
		int mid = (start + end) / 2;
		for (int i = 0; i < n; i++) {
			if (tree[i] > mid)
				total += tree[i] - mid;
		}
		if (total < m) {
			end = mid - 1;
		}
		else {
			result = mid;
			start = mid + 1;
		}
	}
	cout << result << endl;
	return 0;
}