[백준 알고리즘] 2805번 나무 자르기 - C

#include<stdio.h>
#include<algorithm>
#define MAX_SIZE 1000001
using namespace std;

int arr[MAX_SIZE]; // 나무들의 배열
int n, m; // 입력 받는 나무 개수와 가져 가려는 총 나무의 길이
long long sum, value;
long long high = 1000000000;

void search(long long left, int right) { // 이진 탐색, 재귀 함수
        if(left <= right) {
                long long mid = (left + right) / 2;
                sum = 0;

                for(int i = 1; i <= n; i++) { // 원하는 길이만큼 잘리는지를 체크
                        if(arr[i] > mid) {
                                sum += arr[i] - mid;
                        }
                }

                if(sum >= m) { // 원하는 만큼 잘리고 절단기의 높이가 현재보다 높
을 경우 value = mid, 또한 절단기의 높이가 m보다 같거나 크다면
                        value = mid;
                        search(mid + 1, right);
                } else { // 작다면
                        search(left, mid - 1);
                }
        }
}

int main(int argc, char* argv[]) {

        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; i++) {
                scanf("%d", &arr[i]);
        }

        sort(arr + 1, arr + n + 1); // 탐색전 정렬
        search(0, high); // 탐색할 범위
        printf("%lld\n", value);
        return 0;
}