백준 2805번] C++ 나무 자르기

해당 문제는 백준 사이트에서 풀 수 있습니다.

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

※백준 사이트를 풀 때 다른 코딩테스트 사이트와는 다르게 입력과 출력을 해줘야 합니다.

그리고 cout << 로 출력을 해주면 출력하는 속도가 굉장히 느려지기 때문에 printf를 사용하셔야 합니다.

cout<< 와 printf는 함수와 클래스 차이 때문에 cout<<가 디어셈블리상으로 본다면 훨씬 많은 호출이 이뤄지게 됩니다.

1. 문제

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 

정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 

높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 

따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 

예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 

나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. 

(총 7미터를 집에 들고 간다)

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 

이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을 넘기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 

높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

예제 입력 1

4 7
20 15 10 17

예제 출력 1 

15

2. 조건

1. 자를 나무 높이를 정하면 해당 높이만큼 무조건 자르게 된다.

(에를들어 나무가 [20, 30, 15, 10]이 있다고 한고 높이를 15로 맞춘다면 나무는 [15, 15, 15, 10]으로 맞춰진다.

2. 상근이가 갖고싶은 나무의 길이는 M이다.  M의 길이는 자를 나무 높이를 기준으로 잘린 나무 길이의 총 합으로 결정한다.

3. 나무의 높이를 최대한 높게 유지하면서 상근이가 원하는 나무길이 M을 가져갈 수 있는 높이를 구하여라.

3. 풀이

이분탐색으로 풀 수 있습니다. 이분탐색에서 재일 중요한 것은 '어떤 것을 기준으로 찾을 것인가?' 입니다.

여기서 기준이 되는건 나무의 최대 높이가 됩니다. 나무를 높이를 최대한 유지할 수 있는 길이를 구하는 문제이기 때문입니다.

최소값 0 부터 최댓 값 MAX의 중간 값부터 순차적으로 구하면 됩니다.

여기서 최댓 값은 입력받는 나무의 최대 길이가 됩니다.

단, 유의해야할 점은 나무를 잘랐을 때 상근이가 원하는 나무 길이인 M값을 무조건 만족시킬 보장이 없습니다.

위 예제에선 15를 기준으로 잘랐을 때 7이 딱 떨어지지만

[20, 15, 10, 18]로 한다면 15기준으로 짤랐을 때 8이 나오게 됩니다. 

하지만 14기준으로 자른 값보단 15값이 M에 더 가깝기 때문에 15가 정답이 됩니다.

따라서 M에 최대한 가까운 수를 기준으로 하는 나무 높이를 구해야 합니다.

저는 입력받은 나무들을 내림차순으로 정렬한 후 이분탐색을 할 때

기준이되는 mid 값을 뺏을 때 0보다 작으면 break를 했습니다. 

예제에서 처럼 [15, 20, 10, 17]이 있을 때 나무 높이를 15기준으로 잘랐을 경우

10은 안짤려도 되기 때문에 내림차순으로 정렬해서 자를 수 있는 나무들만 자르도록 했습니다.

4. 코드

#include <iostream>

#include <vector>

#include <cstdio>

#include <algorithm>

using namespace std;

long long MAX;

int need_treeLen;

long long result;

long long binary_search(vector<long long>& tree,long long start, long long high) {

    long long mid = (start + high) / 2;

    long long cut_tree = 0;

    

    if (start > high) return result;

    for (size_t idx = 0; idx < tree.size(); idx++) 

        if (tree[idx] - mid < 0) break;

        else cut_tree += tree[idx] - mid;

     

    if (cut_tree >= need_treeLen)    //잘라서 나온 나무 길이가 필요로 하는 나무길이보다 크다면

        result = result < mid ? mid : result;    //M길이에 가까운 근사치를 구한다.

    if (cut_tree > need_treeLen) 

        return binary_search(tree, mid + 1, high);

    else

        return binary_search(tree, start, mid - 1);

}

int main() {

    int N = 0;

    long long temp = 0;

    cin >> N; cin >> need_treeLen;

    vector<long long>tree;

    tree.reserve(N + 1);

    

    for (int i = 0; i < N; i++) {

        cin >> temp;

        tree.emplace_back(temp);

    }

    

    sort(tree.rbegin(), tree.rend());  //내림차순 정렬로 최대 값이 앞으로 오게 한다.

    MAX = tree[0];

    printf("%lld\n", binary_search(tree, 0, MAX));

    return 0;

}