나무자르기.md

DONE_DATE	2025/03/05

나무 자르기

난이도

• 실버 2

문제

https://www.acmicpc.net/problem/2805

알고리즘 분류

• 이분 탐색
• 매개 변수 탐색

회고

• 매개변수 탐색, 영어로는 parametric search 라고 부르는 방법은 조건을 만족하는 값을 구하는 방법이다.
• 사실 이 문제는 작년 8월에 풀었던 문제지만 수민이가 풀어서 다시 풀게 되었다.
• 처음부터 문제가 이진탐색으로 풀어야한다는 것을 알아서 쉽게 풀 수 있었다.

전체코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll cost(int value, vector<int> &trees) {
    ll sum_of = 0;
    for (int t: trees) {
        if (t >= value) { sum_of += t - value; }
    }
    return sum_of;
}

int main() {
    int N, M;

    cin >> N >> M;
    vector<int> trees(N);
    for (int i = 0; i < N; i++) {
        cin >> trees[i];
    }

    int left = 0;
    int right = *max_element(trees.begin(), trees.end());
    int result = 0;

    while (left <= right) {
        int mid = (left + right) / 2;

        ll ct = cost(mid, trees);
        if (ct < M) {
            right = mid - 1;
        } else if (ct >= M) {
            result = mid;
            left = mid + 1;
        }
    }

    cout << result;
}