BOJ 2805 : 나무 자르기

알고리즘 문제 전체 링크

 

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

 

 

정답을 X라고 가정하자. 즉, X 만큼 자를 때, 적어도 M 미터의 나무를 집에 가져간다.

그러면 X - 1 만큼 나무를 자르면 M 미터 보다 더 많은 나무를 가져가게 되고,

X + 1 만큼 나무를 자르면 M 미터 미만의 나무를 집에 가져가게 된다.

 

따라서 BOJ 1939 : 중량제한처럼 이분 탐색을 이용하여 X를 찾을 수 있다.

 

먼저 적당한 값 m으로 나무를 잘라보고, 이 값이 M보다 크면 m 보다 큰 값에서 다시 적당한 값을 정한다.

이 값이 M보다 작으면 m보다 작은 값에서 다시 적당한 값을 정한다.

 

주어지는 나무들의 길이가 1,000,000,000이고 N이 최대 1,000,000이므로, long long type으로 나무를 자른다.

모든 나무에 대해 자를 높이보다 큰 경우, (나무 - 자를 높이)를 더하면 나무를 자르는 함수를 만들 수 있다.

ll cutting(int m)
{
    ll ret;

    ret = 0;
    for (int i = 0; i < N; i++)
        if (tree[i] > m) ret += (tree[i] - m);

    return ret;
}

 

main에서 나무를 자를 최솟값 left = 0, 최댓값 right = 1,000,000,000으로 설정한 후,

이분 탐색을 하면 절단기에 설정할 수 있는 높이의 최댓값을 구할 수 있다.

#include <stdio.h>

typedef long long int ll;

int N;
ll M;
int tree[1001000];

ll cutting(int m)
{
    ll ret;

    ret = 0;
    for (int i = 0; i < N; i++)
        if (tree[i] > m) ret += (tree[i] - m);

    return ret;
}

int main(void)
{
    int left, right, mid, ans;

    scanf("%d %lld", &N, &M);

    for (int i = 0; i < N; i++) scanf("%d", &tree[i]);

    left = 0;
    right = 1000000000;
    ans = -1;
    while (left <= right)
    {
        mid = (left + right) / 2;

        if (cutting(mid) < M) right = mid - 1;
        else ans = mid, left = mid + 1;
    }

    printf("%d\n", ans);
    
    return 0;
}