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

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

풀이

"적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값"을 구해야 하는데,
이 값은 0 이상, 입력받은 나무 중 가장 높은 나무의 높이 이하일 것이다.

나무의 높이의 최대값은 1,000,000,000 이다. 탐색해야 하는 값의 범위가 매우 넓기 때문에 이진 탐색으로 시간을 줄였다.

코드

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int N;
    long long M;
    cin >> N >> M;

    vector<int> v(N);
    int low = 0, high = 0;
    for(int i=0; i<N; i++) {
        cin >> v[i];
        high = max(v[i], high);
    }

    int ans = 0;
    while(low <= high) {
        int height = (low + high) / 2;
        
        long long sum = 0;
        for(int i=0; i<N; i++) {
            if(v[i] <= height) continue;
            sum += v[i] - height;
        }

        if(sum >= M) {
            ans = height;
            low = height + 1;
        } else {
            high = height - 1;
        }
    }
    
    cout << ans;
    return 0;
}

N개의 나무 중 최대값을 알아내서 이진 탐색의 초기 범위를 설정하였다.

주의할 점은 sum이 매우 큰 수가 될 수 있어 long long 형으로 선언해야 한다는 것이다. sum과 비교해야 하는 M도 똑같이 long long으로 선언하였다.

시간복잡도

가장 높은 나무의 높이를 H라고 할 때, 이분 탐색 최대 logH 회이고, 한 탐색에서 나무 배열을 N회 순회하므로
시간복잡도는 O(NlogH) 이다.

---

다른 시도

위 코드는 나무의 최대값만 가져오고, 나무들을 높이에 따라 정렬하지는 않았다. 그래서 이진 탐색을 수행할 때 모든 나무에 대해서 현재 절단기의 높이 H보다 큰지 비교해야 했다.

그렇다면 나무를 정렬하고, 이진 탐색 시에 H보다 작거나 같은 나무는 비교하지 않고 순회를 중단하도록 만들었을 때, 위 코드와 비교하여 시간이 어떻게 달라질지 궁금했다.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int N;
    long long M;
    cin >> N >> M;

    vector<int> v(N);
    for(int i=0; i<N; i++) {
        cin >> v[i];
    }
    
    sort(v.begin(), v.end());

    int ans = 0, low = 0, high = v.back();
    while(low <= high) {
        int height = (low + high) / 2;
        
        long long sum = 0;
        int idx = N-1;
        while(v[idx] > height) {
            sum += v[idx] - height;
            idx--;
        }

        if(sum >= M) {
            ans = height;
            low = height + 1;
        } else {
            high = height - 1;
        }
    }
    
    cout << ans;
    return 0;
}

이 방법은 이전 방법보다 시간이 더 많이 소요된다.

여전히 이진 탐색 시 나무 배열을 순회하는 시간은 O(N)인데, 정렬 O(NlogN) 이 추가되었기 때문이다.