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

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

2805번: 나무 자르기

---

 문제 풀이

이전 문제(BOJ 1654 : 나무 자르기)와 비슷한 문제이다.

다른 점은 딱 맞아떨어지지 않는다는 것이다.

적어도 M미터의 높이의 나무를 가져가야 한다.

즉, 1미터의 나무가 필요할 때 {1, 2, 2} 높이의 나무들이 주어진다면 1미터의 높이에서 잘라야 한다.

 느낀 점

삼항 연산자를 사용해서 중간의 번거로운 계산을 줄였다! 이전과 코드가 똑같아서 그렇게 어렵지 않았다.

 코드

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

using namespace std;

int n, m;
vector<long long> v;

long long binary(long long left, long long right) {
	long long result = 0;
	while (left <= right) {
		long long mid = (left + right) / 2;
		long long tmp = 0;
		for (int i = 0; i < v.size();i++) {
			tmp += (v[i] > mid) ? v[i] - mid : 0;
		}
		if (tmp >= m) {
			if (result < mid) result = mid;
			left = mid + 1;
		}
		else right = mid - 1;
	}
	return result;
}

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

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		long long tmp;
		cin >> tmp;
		v.push_back(tmp);
	}

	sort(v.begin(), v.end());
	cout << binary(0, v[n - 1]);
}