(c++)백준 2805번: 나무 자르기

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

2805번: 나무 자르기

[풀이]

이분 탐색으로 해결하였다.

모든 변수를 long long으로 선언해야 범위에 벗어나지 않았다.

 

#include <iostream>
#include <algorithm>//max
using namespace std;
#define Max 1000001

long long N, M;
long long Tree[Max];

bool cutTree(int height) {
	long long trees = 0;
	for (int i = 0; i < N; i++) {
		if (Tree[i] - height > 0)
			trees += Tree[i] - height;
	}
	if (trees >= M)
		return true;
	return false;
}

void solution() {
	cin >> N >> M;
	long long high = 0;
	for (int i = 0; i < N; i++) {
		cin >> Tree[i];
		high = max(high, Tree[i]);
	}
	long long low = 1;
	long long Maxheight = 0;
	
	//low ~ high높이 위를 잘라서 M미터 이상의 나무를 가져갈 수 있는 최대 높이 구하기
	while (low <= high) {
		long long mid = (low + high) / 2;

		//나무를 잘라서 M미터의 나무 가져갈 수 있으면
		if (cutTree(mid)) {
			Maxheight = max(Maxheight, mid);
			low = mid + 1;
		}
		else
			high = mid - 1;
	}
	cout << Maxheight << endl;
}

int main() {
	solution();
	return 0;
}