[Sort] 백준 2805번 - 나무 자르기

 

 

H 초과하는 나무의 부분만 자른다

자른 나무들의 합 >= M

 

1. 내림차순으로 나무들을 Sort

2. 높이의 최대값이라는 것 = 최대한 잘린 나무들이 M에 가까워야 한다

3. 가장 큰 나무의 높이에서 M을 뺀 만큼 사이의 범위를 이분 탐색하여

      잘린 나무들의 합이 M에 제일 가까운 수 H를 찾는다.

 

처음 코드 

실패 -> 시간 초과

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define endl '\n'
#define DIV 1000000009

int N, M;
int tree[1000000];

bool compare(int a, int b){
    return a>b;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int input;
    cin>>N>>M;
    for(int i=0; i<N; i++){
        cin>>input;
        tree[i]=input;
    }

    sort(tree, tree+N-1, compare);

    int high = tree[0];
    int low = tree[0]-M;
    int h;
    int sum;
    while(low<=high){
        sum = 0;
        h = (low+high)/2;
        for(int i=0; i<N; i++){
            if(tree[i]>h)
                sum += (tree[i]-h);
            else
                break;
            
        }
        if(sum>M)
            low = h+1;
        if(sum<M)
            high = h-1;
        if(sum == M){
            cout<<h<<endl;
            return 0;
        }
    }
    cout<<h<<endl;
    
}

시간 초과라기 보다는 답이 틀렸을 가능성이 있다

바로 sum이 적어도 M을 가져가는 최대값이기 때문에!!

 

if (sum>=M){

   low=h+1;

   ans = h;

}

 

이렇게 처리해주어야 한다

또한 

sort를 따로 돌려줘서 sort에서 걸리는 시간도 앵간하면 줄여주자

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define endl '\n'
#define DIV 1000000009

int N, M;
int tree[1000005];

bool compare(int a, int b){
    return a>b;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int input, max =0;
    cin>>N>>M;
    for(int i=0; i<N; i++){
        cin>>input;
        tree[i]=input;
    }

    sort(tree, tree+N-1, compare);

    int high = tree[0];
    int low = max-M;
    int h;
    long long sum;
    int ans;
    while(low<=high){
        sum = 0;
        h = (low+high)/2;
        for(int i=0; i<N; i++){
            if(tree[i]>h)
                sum += (tree[i]-h);
        }
        if(sum>=M){
            low = h+1;
            ans = h;
        }
        else
            high = h-1;
    }
    cout<<ans<<endl; 
}