백준 - 2805

문제링크

문제요약

나무의 높이와 잘라서 가져가야 하는 나무의 길이 M이 주어진다.

 

나무를 자를 높이 H를 설정하면 일괄적으로 모든 나무를 H높이에서 잘라간다.

 

이때 가져가야하는 나무의 길이 M을 만족하는 최대의 높이를 구해야 한다.

어떻게 풀어야 할까

나무의 최대 수는 백만 개, 나무의 높이는 최대 1억까지 높아진다.

 

잘라야 하는 높이를 0부터 최대 1e9까지로 설정한 뒤 적절한 높이를 출력해야 하는데,

 

문제의 제한시간은 1초이기 때문에 0부터 1e9까지를 이진탐색으로 돌려 시간초과를 해결해야 한다.

수도코드

1. 입력받기
   • 나무의 개수 N과 필요한 나무길이 M을 입력받는다.
   • 배열에 각 나무의 길이를 입력받는다.
2. 이진 탐색 초기화
   • left = 0, right = 1e9으로 설정한다.
3. 이진 탐색 수행
   • 잘라낸 나무 길이 >= 필요한 나무길이 일 경우, mid가 낮을 가능성이 있으므로 절단 높이를 높이기 위해 left를 mid + 1로 설정하고, mid 값을 임시로 정답 후보로 기록한다.
   • 잘라낸 나무 길이 < 필요한 나무길이일 경우, mid가 너무 높다는 뜻이므로 절단 높이를 낮추기 위해 right를 mid - 1로 설정한다.

---

소스코드는 다음과 같다

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

/*
필요한 나무 m미터를 짜를수있는 최대의 높이
즉, 절단기를 최대로 높여 최소한의 나무만을 짤라 m을 만족해야한다
*/

long long n, m;
vector<long long> tree;

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        long long tmp;
        cin >> tmp;
        tree.push_back(tmp);
    }

    long long left = 0, right = 1e9;
    long long ans = 0;
    while (left <= right) {
        long long mid = (left + right) / 2;
        long long tmp = 0; // 얻은나무
        for (const long long e : tree) {
            if (e > mid) //잘라서 얻은나무
                tmp += e - mid;
        }
        if (tmp >= m) { //나무를 많이자른경우
            ans = mid;
            left = mid + 1;
        }
        else if (tmp < m) {
            right = mid - 1;
        }
    } 
    cout << ans;
}