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

 

1) 문제설명

백준 Online Judge 2805번 나무 자르기

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

2805번: 나무 자르기

 

2) 아이디어

m미터의 나무를 잘라서 가져가야 하므로 이진 탐색을 이용하여 입력받은 배열들에서 mid를 빼고 그 값들(temp)을 다 더해 필요한 양만큼 가져가야 한다.

가져가야 할 양보다 temp 가 더 작다면 나무를 더 작게 잘라야 하고

가져가야 할 양보다 temp가 크거나 같다면 나무를 더 크게 잘라야 한다.

이분 탐색을 계속 돌면서 높이의 최댓값을 저장하고 출력한다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
long long arr[1000001];
long long n, m;
long long result;
void binary_search(long long start, long long end) {
	long long temp = 0; // 나무를 자르고 가져갈 양의 합
	long long mid = (start + end) / 2;
	if (start == end) {
		return;
	}
	for (int i = 0; i < n; i++) {
		if (arr[i] > mid) {
			temp = temp + (arr[i] - mid);
		}
	}
	if (temp < m) { // 가져갈 양이 필요한 양보다 작다면 더 적게자르고
		binary_search(start, mid);
	}
	else if(temp >= m) { // 가져갈양이 필요한 양보다 크거나 같다면 더 많이 자른다
		result = max(result, mid);
		binary_search(mid + 1, end);
	}
	
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	sort(arr, arr + n);
	binary_search(1, arr[n - 1]);
	cout << result;
}