[BOJ]2805번: 나무 자르기 (c++)

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

2805번: 나무 자르기

 

이분 탐색

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

using namespace std;

// limit높으로 자르고 남은 길이 합 구하기
long long get_cut_off_sum(vector<int> &trees, long long limit)
{
	long long left = 0;
	for (int tree : trees)
	{
		if (tree - limit > 0)
		{
			left += tree - limit;
		}
	}
	return left;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	// 입력
	int N, M;
	cin >> N >> M;
	vector<int> trees(N);
	int max_tree = 0;
	for (int i = 0; i < N; ++i)
	{
		cin >> trees[i];
		if (max_tree < trees[i])
		{
			max_tree = trees[i];
		}
	}

	// 이분탐색
	long long answer = 0;
	long long left = 0;
	long long right = max_tree;
	while (left <= right)
	{
		long long mid = (left + right) / 2;
		long long sum = get_cut_off_sum(trees, mid);

		// 자른 합이 M보다 크거나 같다면 더 높이 자를 수 있는지 확인한다
		if (sum >= M)
		{
			// 자를 수 있는 최대 높이 갱신
			answer = max(mid, answer);
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
	}

	// 출력
	cout << answer;

	return 0;
}

 

 

랜선자르기 문제와 비슷한 유형이다.

 

나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다.
(1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

나무의 높이의 합은 항상 M을 넘기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다.

마찬가지로 자료형의 크기를 주의해야 한다.

 

 

이분탐색으로 단순히 값을 찾는 것이 아니라,

찾아진 값을 기준으로 또 다른 조건을 충족하는 답을 찾을 때에는

재귀함수보다는 반복문을 이용한 이분탐색이 더 간편한 것 같다.