#2085번 나무 자르기 (C++)

링크 : www.acmicpc.net/problem/2805

2805번: 나무 자르기

예전에 푼 적이 있던 문제였으나, 기회가 되어 다시 한번 풀었다.

 

이 문제에서 주의할 점은 다음과 같다.

1. 절단 높이가 나무보다 더 큰 경우에도 절단이 가능하다. 

ex : 나무 15, 절단 높이 20 -> 이때 나무를 자르고 남는 길이는 0으로 여긴다. 

2. 때문에 절단기에 설정 가능한 높이가 아닌, 최대의 높이를 선정하는 것이 문제다.

3. 나무의 높이를 크게 받을 수 있으므로, 변수형을 잘 설정해야한다.

 

문제풀이는 다음과 같다. 

1. 값을 모두 입력 받는다. 이때, 가장 높은 나무의 값은 따로 저장한다. 

2. while문을 설정한다. 조건은 절단 길이의 양 끝 구간을 mini, maxi라고 가정했을때

mini가 maxi이하인 경우에만 while문이 허용된다. 

3. mini와 maxi의 중간값을 구한다. 모든 나무의 길이에서 중간값을 뺀 값을 누적한다. 

(*이때 나무의 길이가 중간값보다 큰 경우에만 뺀 값을 누적한다. 이 외에는 어차피 0이 누적되니 계산하지 않아도 된다.)

4. 누적된 값이 m이상일 경우, 더 자를 수 있음을 의미한다. 때문에 mini의 값을 중간값의 +1로 설정한다.

5. 누정값이 m 미만일 경우, 해당 값 자제가 불가능이며 동시에 더 자를 수 없음을 의미한다.

때문에 maxi의 값을 중간값의 -1로 설정한다. 

6. 결과값으로 maxi를 출력한다.

 

#include <iostream>
#include <algorithm>
using namespace std;

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

    unsigned long long int n, m, mini, maxi, mid, temp, ans =0;
    cin >> n >> m;
    unsigned long long int trees[n];
    for(int i=0; i<n; i++){
        cin >> trees[i];
        if(trees[i]>=maxi) maxi = trees[i];
    }
    while(mini<=maxi){
        temp = 0;
        mid = (mini+maxi)/2;
        for(int i=0; i<n; i++) if(trees[i]>mid) temp += trees[i]-mid;
        if(temp>=m) mini = mid+1; // 더 짤라야해
        else if(temp<m) maxi = mid -1;
    }
    cout << maxi << "\n";
    return 0;
}