[백준] 2805 - 나무 자르기

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

2805번: 나무 자르기

 

INPUT의 개수가 1,000,000 개로 모든 높이에서 잘라 볼 경우 O(NM) 의 시간 복잡도가 소요되어 시간초과가 발생할 것이다.

 

따라서 자를 높이를 이분탐색을 통해 찾아 시간 복잡도를 O(N lgM) 까지 줄일 수 있다.

 

<C++ 코드>

 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
 
int main(){
    long long n, m, right = 0;
    vector<long long> tree;
    scanf("%lld %lld", &n, &m);
    for(int i=0; i<n; i++){
        long long tmp;
        scanf("%lld", &tmp);
        tree.push_back(tmp);
        right = max(right, tmp);
    }
 
    long long mid = right / 2, left = 0, re = 0;
    while(right >= left){
        long long sum = 0;
        for(int i=0; i<n; i++){
            if(tree[i] > mid) sum += tree[i] - mid;
        }
        if(sum >= m){
            if(re < mid) re = mid;
            left = mid + 1;
            mid = (left + right) / 2;
        }
        else{
            right = mid-1;
            mid = (left + right) / 2;
        }
    }
    printf("%d", re);
 
    return 0;
}