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

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

2805번: 나무 자르기

---

나무의 높이가 최대 10억이기 때문에 모든 높이에 대해 잘린 나무의 길이를 계산하면 시간초과가 발생합니다. 

따라서 나무 자르기 문제는 이분탐색을 이용해야합니다. 

 

중요한 점은 나무의 개수가 최대 백만개이고, 높이는 최대 10억이기 때문에, 잘린 나무의 높이를 계산할 때, 결과 값을 저장하는 변수의 자료형이 long long이 되어야 한다는 것입니다. 

 

또한 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 계산해야하기 때문에

이분탐색 시 높이가 height 일 때 잘려진 나무의 높이가 m보다 크거나 같고, height + 1일 때 잘려진 나무의 높이가 m보다 작으면 height가 절단기의 최대 높이이므로, 이분탐색을 벗어나도록 구현해야합니다. 

 

아래는 전체 코드입니다. 

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

int arr[1000000];
int n, m;

// 높이를 height로 했을 때, 가져갈 수 있는 나무의 길이를 계산하는 함수
// 각각의 높이는 10억보다 작거나 같기 때문에 반환형은 long long이 되어야 한다.
long long length(int height){   
    long long l = 0;
    for(int i = 0; i < n; i++)
        if(arr[i] > height) l += arr[i] - height;
    return l;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    for(int i = 0; i < n; i++)  
        cin >> arr[i];
    
    // 가능한 절단기의 범위 설정 
    // 상근이는 필요한 나무를 항상 가져갈 수 있기 때문에 절단기의 최대 높이는 나무의 최대 높이 -1
    int high = *max_element(arr, arr + m); - 1; 
    int low = 0;

    while(high > low){  // 이분탐색
        int height = (high + low) / 2;
        long long l = length(height);
        
        // m미터의 나무를 자르기 위해서 설정할 수 있는 절단기의 최대 높이인 경우
        if(l >= m && length(height + 1) < m){   
            break;
        }else if(l < m){  // 나무가 부족한 경우
            high = height - 1;
        }else if(l > m){ // 나무가 충분한 경우
            low = height + 1;
        }
    }

    cout << (high + low) / 2;
}

 

아래는 문제 풀이에 사용된 테스트 케이스입니다.

4 5
20 15 10 17

4 5
20 15 10 17

4 3
20 15 10 17

4 1
20 15 10 17

4 4
1 1 1 1

4 17
4 4 4 4