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

🌽 문제

🥕 입출력

🥔 풀이

랜선 자르기 2탄 같은 문제다.
이분탐색으로 필요한 만큼의 나무를 처리할 최대 길이를 찾아나가는 방식이다.

🥬 코드

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

int N, K;
vector<int> v;

long long solution() {
	long long l = 0;
	long long r = v[N - 1];
	long long m, sum, h = 0;
	while (l <= r) {
		m = (l + r) / 2;
		sum = 0;
		for (int i = 0; i < N; i++) {
			if (v[i] <= m) continue;
			sum += v[i] - m;
		}
		if (sum < K) {
			r = m - 1;
		}
		else {
			l = m + 1;
			h = max(h, m);
		}
	}

	return h;
}

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

	cin >> N >> K;
	v.resize(N);
	for (int i = 0; i < N; i++) cin >> v[i];
	sort(v.begin(), v.end());

	cout << solution();

	return 0;
}

🥜 채점

이분탐색 좋다..