Beakjoon 2805 나무 자르기

06 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/2805

나의 풀이

i번째 나무의 높이를 L_i, 절단기의 높이를 H라고 할 때 각 나무에서 나오는 나무 조각의 길이는 L_i - H (단 L_i > H) 이다. 이를 통해 각 나무에서 나오는 모든 나무 조각의 길이의 합이 M 이상인 H의 최댓값을 찾는다.

이진 탐색을 이용하면 H의 최댓값을 찾을 수 있다.
H의 범위는 다음과 같기 때문에 이 범위 안에서 이진 탐색을 수행한다. 0 <= H <= max(L_i)

풀이 코드 : 2805 나무 자르기

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int N, M, num, _max = -1;
    vector<int> length;
    cin>>N>>M;

    for(int i=0;i<N;i++){
        cin>>num;
        length.push_back(num);
        if(_max < num) _max = num;
    }

    sort(length.begin(), length.end());

    int start = 0;
    int end = _max;
    int mid, answer = 0;
    long long total;
    while(start<=end){
        mid = (start+end)/2;
        total = 0;
        for(int i=0;i<N;i++){
            if(length[i] - mid > 0)
                total += length[i] - mid;
        }

        if(total >= M){
            answer = mid;
            start = mid + 1;
        }
        else{
            end = mid - 1;
        }
        
    }

    cout<<answer;

}

채점결과