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

백준 - 2805

---

풀이

입력받은 높이들 중에서 최대높이를 찾아 last로 지정하고, 절단기로 자를 나무의 높이(mid)를 기준으로 이분탐색을 사용해 풀이했다.

mid보다 높은 높이의 나무만 자르며 필요한 M미터를 충족시킬때 result로 갱신해주었다.

---

소스코드

#include <stdio.h>
int arr[1000001];
int main(){
    int N, M;
    long long last = 0;
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++){
        scanf("%d", &arr[i]);
        last < arr[i] && (last = arr[i]);
    }
    long long temp = 0, result = 0, first = 0, mid;
    while (first <= last){
        mid = (first + last) / 2;
        temp = 0;
        for (int i = 0; i < N; i++)
            arr[i] > mid && (temp += (arr[i] - mid));
        if (temp >= M && result < mid)
            result = mid;
        result < mid ? last = mid-1 : (first = mid+1);
    }
    printf("%lld\n", result);
}

---

출처

2805번: 나무 자르기