[백준 2805] 나무 자르기

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

2805번: 나무 자르기

#include <cstdio>
#include <iostream>
#include <algorithm>
int N;
long long int M;
int tree[1000000 + 10];

void input(void)
{
	scanf("%d %lld", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%d", &tree[i]);
	}
}

int get_tree(void)
{
	std::sort(tree, tree + N);	// 나무 오름차순 정렬

	int s = 0;				// 나무를 자르지 않고 다 가져가는 경우가 있을 수 있다. 
	int e = tree[N - 1];	// 절단기의 최대 높이는 나무의 최대 높이
	int pivot = 0;

	while (s <= e) {
		pivot = (s + e) / 2;

		long long int total = 0;
		for (int i = N - 1; i >= 0; i--) {
        	// 나무의 높이가 절단기보다 높을 때만 연산한다. 
			if (tree[i] > pivot) total += (tree[i] - pivot);
		}
		if (total == M) return pivot;
		else if (total < M) e = pivot - 1;	// 절단기의 높이가 작을수록 total 늘어남
		else if (total > M) s = pivot + 1;	// 절단기의 높이가 클수록 total 줄어듦
	}
	return e;
}

int main()
{
	input();
	int max = get_tree();
	printf("%d", max);
	return 0;
}

 

생각할 거리가 몇가지 있다. 

1. 절단기로 나무를 잘라낸 만큼을 가져가는 것이므로, 절단기의 길이가 길수록 가져가는 나무가 적어지고 길이가 짧을수록 가져가는 나무가 많아진다. 

2. 절단기의 최솟값은 "0" 이다. 모든 나무를 자르지 않고 그대로 가져가는 경우가 있을 수 있다. 한편 이 때 최악의 경우를 생각해보면 1,000,000그루의 나무의 높이가 모두 1,000,000,000일 수 있다. 이때 total 값은 int 범위를 벗어나기 때문에 입력받는 M과 total값의 타입을 long long int로 설정해 주어야 한다.