[BaekJoon][2805] 나무 자르기

BAEKJOON ONLINE JUDGE

2805 나무 자르기

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

H 높이를 찾는 이진 탐색을 하면 된다.

H 값을 기준으로 잘린 나무의 합이 필요한 값보다 크면 더 큰 H를 찾아야 하고, 잘린 나무의 길이 합이 M보다 작으면 H는 더 낮아야 한다.

여기서, 문제의 특성을 잘 살펴보면 H 값이 변하면 잘린 나무의 값은 무조건 변하게 된다.

따라서, 잘린 나무의 길이의 합이 M과 같으면 그 H값이 바로 최대값이다.

하지만 여기서 잘린 나무의 길이 합이 딱 M과 같지 않을 수도 있기 때문에

그럴 경우에는 합이 M보다 큰 마지막 경우의 end 값을 출력해 주어야 한다.

(end를 출력하는 이유는 조건을 만족하는 마지막 middle에서 + 1을 한 값이 start가 되고, 

 계속 범위를 줄여 탐색을 하였을 때 끝나는 값이 start - 1이다. (이것은 직접 손으로 탐색 범위를 계산해 보면 알 수 있다.)

 그리고 이 start - 1은 조건을 만족하는 마지막 middle 값이기 때문에 M 이상의 나무를 얻을 수 있는 최대 H이다.)

#include <stdio.h>
 
int n, m;
int tree[1000000];
 
int main()
{
    int i;
    int start = 1, end = 0, sum;
    long long int middle;
 
    scanf("%d %d", &n, &m);
 
    for (i = 0; i < n; i++) {
        scanf("%d", &tree[i]);
        if (tree[i] - end > 0)   end = tree[i];
    }
 
    while (start <= end) {
        middle = (start + end) / 2;
        sum = 0;
 
        for (i = 0; i < n && sum <= m; i++) {
            if (tree[i] - middle > 0)
                sum += tree[i] - middle;
        }
 
        if (!(sum - m)) {
            printf("%d\n", (int)middle);
            return 0;
        }
        else if (sum - m > 0)
            start = middle + 1;
        else end = middle - 1;
    }
 
    printf("%d\n", end);
 
    return 0;
}