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

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

2805번: 나무 자르기

알고리즘 분류

• 이분 탐색
• 매개 변수 탐색

 

문제 풀이

나무의 수 N과 가져가야하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)
그리고 나무의 높이들이 주어진다. ( 0 ≤ 나무 높이 ≤ 1,000,000,000)
이 때, 적어도 M미터의 나무를 가져가기 위한 절단기 높이의 최댓값을 찾으면 된다.

단순하게 주어진 절단기 높이를 나무의 높이 중에 최대값부터 1씩 낮추면서 가져갈 수 있는 나무의 길이가 M이 될때를 찾는 다면 시간 복잡도를 O(N * 나무 높이)이라고 볼 수 있다. 1,000,000 * 1,000,000,000 은 10의 15승으로 시간초가가 날 것이다.

그렇다면 어떻게 풀 것 인가!
절단 높이를 시간 내에 찾기위해 이분 탐색을 이용할 것이다.

 

코드 구현

#include <iostream>
using namespace std;

int trees[1000000];

int main(){
    int N, M; cin >> N >> M;
    int s=0, e=0, m;
    for(int i=0; i<N; i++){
        cin >> trees[i];
        e = max(e, trees[i]);
    }

    long long sum;
    int answer;
    while(s <= e){
        m = (s + e + 1) / 2;
        sum = 0;
        for(int i=0; i<N; i++){
            if(trees[i] - m <= 0) continue;
            sum += trees[i] - m;
        }
        if(sum > M){
            s = m + 1;
            answer = m;
        } else if(sum < M){
            e = m - 1;
        } else {
            answer = m;
            break;
        }
    }

    cout << answer;
}