3. 2805 나무 자르기

원본 출처 : https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

문제 풀이 : 

#include <stdio.h>
#define MAX 1000010     
int N, M;
int arr[MAX];//나무의 최대 수
void quick_sort(int s, int e) {
	int L, T, P = e, temp;
	if (s >= e) return;  //종료 조건
	for (L = s, T = s; L < e; L++) {
		if (arr[L] < arr[P]) {
			if (L != T) { temp = arr[L]; arr[L] = arr[T]; arr[T] = temp; }
			T++;
		}
	}
	if (P != T) { temp = arr[P]; arr[P] = arr[T]; arr[T] = temp; }
	quick_sort(s, T - 1);
	quick_sort(T + 1, e);
}
long long solve(int m) {
	long long sum_tree = 0;
	for (int i = 0; i < N; i++) {
		if (arr[i] > m) {
			sum_tree += arr[i] - m;
		}
	}
	return sum_tree;
}
int main() {
	int i;
	long long m, s, e, sol = 0;
	scanf("%d", &N);    //나무의 수
	scanf("%d", &M);    //나무의 길이

	for (i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}
	quick_sort(0, N - 1);
	s = 0;  //s는 가장 작은 수 
	e = arr[N - 1]; //e는 가장 큰 수
	scanf("%d", &M);

	while (s <= e) {
		m = (s + e) / 2;    //상한가를 mid로 계산
		if (solve(m) < M) {
			//H가 높으면 줄여본다.
			e = m - 1;
		}
		else if (solve(m) >= M) {
			//H가 낮으면 높혀본다
			sol = m;
			s = m + 1;
		}
	}
	printf("%lld\n", sol);
	return 0;
}

예산 문제와 같은 개념의 문제이다. 예산은 최대한 많은 예산을 줘야 했고 나무는 적어도 얼마나 들고 가면 되냐 하는 문제이다. 입력되는 값이 크기 때문에 long long 을 써주어야 한다.