[210616][백준/BOJ] 2805번 나무 자르기

문제

입출력

풀이

이분 탐색으로 문제를 풀 수 있다.
M미터의 나무를 구하기 위해 목재절단기에 설정할 수 있는 최대 높이 H를 구하는 문제이다.

상근이가 7미터의 나무를 가져가야하며 나무의 높이들이 20, 15, 10, 17 일때 절단기에 설정하는 높이 H를 15로 설정하면 (20-15 = 5) + (17-15 = 2) = 7이 된다.

따라서 H를 구하기 위해 1미터부터 나무들의 최대 높이까지 이분탐색으로 탐색을 하면서 상근이가 M미터의 나무를 가지고 가기 위해 절단기에 설정하는 H를 구할 수 있다.

1. 이분 탐색을 위해 left = 1, right = 나무들의 최대값으로 초기화한다.
2. 이분 탐색을 하면서 자른 나무의 합이 M보다 클 경우에는 left 값을 mid + 1로 초기화해준다.
3. 이분 탐색을 하면서 자른 나무의 합이 M보다 작을 경우에는 right 값을 mid - 1로 초기화해준다.
4. 적어도 M미터의 나무를 가져가기 위해 설정할 수 있는 최대 H를 구하는 문제이므로 자른 나무의 합이 M보다 클 때의 가장 큰 mid가 정답이 된다.

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

	ll n, m, maxH = 0;
	cin >> n >> m;
	vector<ll> V(n);

	for (int i = 0; i < n; ++i)
	{
		cin >> V[i];
		maxH = max(maxH, V[i]);
	}

	ll left = 1, right = maxH, ans = 0;

	while (left <= right)
	{
		ll mid = (left + right) / 2;
		ll sum = 0;

		for (int i = 0; i < n; ++i)
		{
			if(V[i] > mid)
				sum += (V[i] - mid);
		}

		if (sum >= m) // 적어도 m미터의 나무를 가져갈려고함
		{
			ans = max(ans, mid);
			left = mid + 1;
		}
		else
			right = mid - 1;
	}
	cout << ans << '\n';
}