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

 

풀이)

이분탐색을 이용해서 값을 가져가야할 나무의 최댓값을 찾는 문제이다.

이 문제의 경우 특정 값을 직접 찾는 것이아니며, 숫자 범위에 있기 때문에 정렬을 필요로하지않는다.

코드는 다음과 같다.

 

코드)

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

long long getTree(vector<int>& trees, int mid) {
	
	long long total = 0;

	for (int tree : trees) {
		if (tree > mid) {
			total += tree - mid;
		}

	}
	return total;

}


int main()
{
	int n, m;

	cin >> n >> m;

	vector<int> trees(n);


	for (int i = 0; i < n; ++i)
		cin >> trees[i];



	int low{};
	int high = *max_element(trees.begin(), trees.end());
	int result{};


	while (low <= high){
		int mid = low + (high - low) / 2;
		long long wood = getTree(trees, mid); 
		if (wood >= m) {
			result = mid;
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}


	}

	cout << result;
}

 

백준문제의 정답비율이 낮은 문제는 대부분이 어려운 문제보단, 이렇게 자료형의 범위를 넘어가게 만든다..

주의하자..