[백준/BOJ/C언어] 2805번 :: 나무 자르기

문제 링크

 

Solution

---

 

나무를 자를 특정 높이를 구해야 한다. 즉, 특정 숫자를 구해야 하는 것이다. 이 숫자는 어떤 조건을 만족해야 한다. 조건이 무엇인지는 차치하고, 이 두 가지만 먼저 고려해 보자. 전형적인 탐색 알고리즘 문제와 비슷하다. 그래서 이분 탐색을 사용했다. 다만 이미 입력받거나 해서 정해진 특정 숫자를 찾는게 아니라, 나무들의 배열에서 이 숫자보다 큰 높이를 가진 나무들을 잘랐을 때 잘린 부분의 합이 M이 넘는다는 조건을 만족하는 숫자를 찾아야 하는 게 다른 점이다. 또 하나 주의해야 할 점은 그렇게 해서 조건을 만족하는 최댓값을 찾아야 한다는 것이다. 코드에서 ans가 등장한 이유이다. 가령, 입력으로 나무 개수가 2개, 필요한 나무의 길이가 3, 각각의 나무의 길이가 2인 경우에는 s = 0, e = 1, mid = 0에서 s = 1, e = 1, mid = 1로 탐색이 이어지게 된다. 이후 s가 e보다 커지므로 ans가 없다면 mid=1을 출력하게 되는데, 이는 답이 아니다. 즉, 탐색을 끝냈을 때 mid가 정답이 되지 않을 수도 있는 것이다.

 

 

Code

---

 

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int tree[1000001];
int N, M;
long long sum, ans;
long long HIGH = 1000000000;

void getTree(long long s, int e) {
    if (s <= e) {
        long long mid = (s + e) / 2;
        sum = 0;
        for (int i = 1; i <= N; i++) {
            if (tree[i] > mid) {
                sum += tree[i] - mid;
            }
        }

        if (sum >= M) {
            ans = mid;
            getTree(mid + 1, e);
        }
        else {
            getTree(s, mid - 1);
        }
    }
}


int main() {
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &tree[i]);
    }

    sort(tree + 1, tree + 1 + N);
    getTree(0, HIGH);
    printf("%lld", ans);

    return 0;

}