2805-나무 자르기

처음에 아래와 같이 정말 단순하게 풀었더니 시간초과가 나왔다.

생각해보니 input의 개수가 1,000,000 개가 되면 시간이 O(NM)이 되어 시간 초과가 나올 것이다.

 

#include <iostream>
#include <vector>

using namespace std;

// N : 나무의 수 , M : 집으로 가져가려는 나무의 길이

int N,M;
int tree[1000000]={0,};
int MAX=0;

int main(void)
{
    vector <int> tree;
    
    cin >> N >> M;
    
    for(int i=0;i<N;i++){
        int len;
        
        cin >> len;
        tree.push_back(len);
        if(MAX < tree[i])   MAX = tree[i];
    }
    

    while(MAX >= 0){
        int height=0;
        MAX--;
        
        for(int i=0;i<N;i++){
            if(tree[i] > MAX)   height += tree[i] - MAX;
        }
        
        if(height >= M)  break;
    }
    cout << MAX;
    return 0;
    
}

 

그래서 알고리즘을 찾아봤다. 이분탐색