언제나 처음처럼

[문제 링크]

함정이 있는 이분 탐색 문제였다.

나무를 자르는 높이가 낮을수록 얻어가는 나무는 증가한다. 즉 나무를 자르는 높이(N)과 얻어가는 나무의 양은 반비례한다.

따라서, 어떤 높이(mid)를 기준으로 나무를 잘랐을 때 얻어가는 나무의 양이 필요한 양(M)보다 작다면 mid보다 높이 자르는 경우는 고려하지 않아도 되며, 이 사실을 바탕으로 이분 탐색을 사용하는 조건을 만족하게 된다.

알고리즘은 다음과 같다.

먼저 나무들의 높이를 vector에 입력받은 다음 오름차순으로 정렬하자.

그 다음 가장 낮은 높이(lower)를 0으로 하고, 가장 높은 높이(upper)를 벡터의 마지막 원소로 하여

(lower + upper) / 2 를 mid 로 이분 탐색을 시작한다.

vector의 모든 원소에 대하여 v[i] - mid가 0보다 클 경우 sum 변수에 값을 누적 시킨다.

만약 sum이  M보다 작을 경우 mid 높이보다 같거나 높은 경우는 버려도 무방하므로 upper 값을 mid - 1로 바꿔준다.

sum이 M보다 같거나 클 경우 조건을 만족하므로 result 변수에 mid를 저장하고, 최대 높이를 찾기 위해 lower 값을 mid + 1로 바꿔준다.

(ps. 여기서 함정이 있는데 적어도 M개를 가져가야 하므로, sum이 M보다 크거나 같은 경우에 result 변수를 갱신해야한다. 작거나 같은 경우에 result 변수를 갱신하게 되면 오답이 출력된다.)

끝으로, lower이 upper보다 커질 때가지 위 작업을 반복하게 되면 result 변수에는 적어도 M미터의 나무를 얻기 위한 최대의 높이가 저장된다.

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

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

	int N, M;
	cin >> N >> M;
	vector<int> tree(N);

	for (int i = 0; i < N; i++)
		cin >> tree[i];

	sort(tree.begin(), tree.end());
	
	int lower = 0, upper = tree[N-1], result;
	while (lower <= upper)
	{
		int mid = (lower + upper) / 2;
		long long sum = 0;
		for (int i = 0; i < N; i++)
		{
			if (tree[i] < mid) continue;
			sum += tree[i] - mid;
		}
		if (sum >= M)
		{
			result = mid;
			lower = mid + 1;
		}
		else
		{
			upper = mid - 1;
		}
	}
	cout << result << endl;
	return 0;
}

알고리즘 200일 프로젝트 - 45 day