백준 2805 (나무 자르기) c++

문제

2805번: 나무 자르기

n개의 나무와 나무 높이가 주어진다면 최소 m미터의 나무높이를 집에 가져가기 위해 나무를 자를 수 있는 높이의

최댓값을 구하는 문제입니다.

예를들어 n이 4이고 m은 7 이면 나무의 높이들은 각각 20, 15, 10, 17 이라고 한다면

다음과 같은 그림이 그려집니다.

이러한 나무들을 15 높이로 자르게 되면 최소한 7을 자를 수 있는 최대높이가 됩니다.

따라서 답은 15가 됩니다.

 

특정높이(k)를 선택했을 때 m이상을 얻을 수 있다면 k미만의 높이도 모두 가능합니다.

k가 낮아질수록 얻는 나무의 양은 늘어나고 

k가 높아질수록 얻는 나무의 양은 줄어듭니다.

따라서 k에 따라 얻는 나무의 양은 배열로 표현하면 내림차순으로 정렬된 상태입니다.

 

이는 parametric search를 활용하는 단조성의 특징입니다.

int s = 0;
int e = 1000000000;
int ans = 0;
while (s <= e) {
    int mid = (s + e) / 2;
    if (sol(mid)) {
        ans = max(ans, mid);
        s = mid + 1;
    }
    else e = mid - 1;
}
cout << ans;
 
bool sol(int mid) {
    ll sum = 0;
    for (int i = 0; i < n; i++)
        sum += max(0, arr[i] - mid);
    if (sum >= m)return true;
    else return false;
}

특정높이 k에서 m이상의 나무를 얻을 수 있다면 true를 반환하고 계속해서 이분탐색 하듯이 mid값을 높여가면서

최댓값을 찾습니다.

그렇지 않으면 false를 반환하고 k의 높이를 줄여 다시 탐색합니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
#define inf INT_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
int n,m;
int arr[1000001];
bool sol(int mid);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n>>m;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    
    int s = 0;
    int e = 1000000000;
    int ans = 0;
    while (s <= e) {
        int mid = (s + e) / 2;
        if (sol(mid)) {
            ans = max(ans, mid);
            s = mid + 1;
        }
        else e = mid - 1;
    }
    cout << ans;
 
    return 0;
}
bool sol(int mid) {
    ll sum = 0;
    for (int i = 0; i < n; i++)
        sum += max(0, arr[i] - mid);
    if (sum >= m)return true;
    else return false;
}