백준_2805_나무자르기

 

 

지난번 랜선자르기와 비슷한 문제입니다.

 

https://sol248.tistory.com/32

백준_1654_랜선자르기

 

이 문제와 같이 이분 탐색으로 문제를 풀어보겠습니다.

 

 

위 문제와 동일한 방식으로 풀었습니다.

 

전체 코드)

#include <stdio.h>

int binary_search(int tree_need, int max, int min, int tree[], int size);

int main(void)
{
    int n; // 나무의 수 (1~1,000,000)
    int m; // 집으로 가져가려고 하는 나무의 길이 (1~2,000,000,000)

    scanf("%d %d", &n, &m);

    int tree[n];
    int max = 0, min = 0, size = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &tree[i]);
        size++;
        if (tree[i] > max)
            max = tree[i];
    }
    printf("%d\n", binary_search(m, max, min, tree, size));
    return 0;
}

int binary_search(int tree_need, int max, int min, int tree[], int size)
{
    int mid = (max + min) / 2;
    while (min != mid)
    {
        long long tmp = 0;
        long long tr = 0;
        for (int i = 0; i < size; i++)
        {
            tmp = tree[i] - mid;
            if (tmp < 0)
                tmp = 0;
            tr += tmp;
        }

        if (tr < tree_need)
        {
            max = mid;
        }
        else if (tr >= tree_need)
        {
            min = mid;
        }
        mid = (max + min) / 2;
    }
    return mid;
}