[2805] 나무 자르기

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

2805번: 나무 자르기

 

---

 

🔎 해결 방법 

[2110] 공유기 설치, [1654] 랜선 자르기와 아주 유사한 문제!

처음에 문제가 잘 이해가 안됐는데, 

위의 그림과 같이 내가 만약 절단기의 높이를 15로 정했다면 내가 가져갈 수 있는 나무의 길이는 5+0+0+2=7이 된다.

나무는 위에서부터 자르기 때문에 윗부분만 가져갈 수 있는 것!

---

1. 나무의 높이를 오름차순 정렬

2. 이분 탐색 문제에서 left의 초기값은 대부분 1이었는데 여기서는 나무의 높이가 0보다 크거나 같은 정수이기 때문에 left = 0, right = (가장 높은 나무의 길이)로 초기화 해줘야 함

3. mid값을 자르고자 하는 높이로 설정한 다음 cut 함수의 반환값이 n보다 크거나 같다면 자를 높이를 더 높여야 하므로 left = mid + 1로 업데이트!

하지만 cut 함수의 반환값이 n보다 작다면 높이를 너무 높게 설정한 것이기 때문에 right = mid - 1로 업데이트!

cut 함수는 자르고자 하는 높이를 설정한 경우, 총 상근이가 가져갈 수 있는 나무의 길이를 반환해준다.

그리고 가장 중요한 것은!!!!!!

left, right, mid, answer, check 함수의 반환값, cut 함수의 반환값 모두 long long 형으로 설정해주어야 한다!!

상근이가 기존에 가지고 있던 나무의 개수가 1,000,000개이고 각각의 높이가 모두 1,000,000,000인 경우 절단기의 높이를 1미터로 설정한다면 999,999,999미터 길이의 나무가 1,000,000개 있는 것이므로 int 형으로는 이 크기를 감당할 수 없기 때문에 

 8바이트 크기를 감당할 수 있는 long long 형 으로 설정해주어야 한다!

 

---

 

💡 내 코드(C++)

// [2805] 나무 자르기
// https://www.acmicpc.net/problem/2805
// 이분 탐색

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

long long check(vector<long long> &tree, int n, long long m);
long long cut(vector<long long> &tree, int n, long long height);

int main(void)
{
    int n; // 나무의 수
    long long m; // 상근이가 집으로 가져가려고 하는 나무의 길이
    scanf("%d %lld", &n, &m);
    vector<long long> tree(n);
    
    for (int i = 0; i < n; i++) {
        scanf("%lld", &tree[i]);
    }
    sort(tree.begin(), tree.end());
    printf("%d\n", check(tree, n, m));
}

long long check(vector<long long> &tree, int n, long long m)
{
    long long left = 0;
    long long right = tree[n - 1];
    long long answer = 0;
    
    while (left <= right) {
        long long mid = (left + right) / 2;
        if (cut(tree, n, mid) >= m) {
            left = mid + 1;
            answer = mid;
        }
        else {
            right = mid - 1;
        }
    }
    
    return answer;
}

long long cut(vector<long long> &tree, int n, long long height)
{
    long long length = 0;
    for (int i = 0; i < n; i++) {
        // 자르고자 하는 높이보다 나무가 긴 경우 -> 자를 수 있음
        if (tree[i] > height)
            length += tree[i] - height;

        // 나무가 짧아서 자를 수 없는 경우
        else
            ;
    }
    
    return length;
}