백준 s2 2805 나무 자르기 c++

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

2805번: 나무 자르기

 

풀이

문제 설명과 풀이는 https://kyj0032.tistory.com/52와 유사하게 parametric search 썼음

 

조건(잘린 나무 합이 M 이상)에 맞는 절단기 높이 H의 최댓값을 구해야 함.

절단기 높이 H는 최대 10^9으로 1씩 내려가며 완전탐색을 할 수가 없음. 대신 이분탐색으로 높이 H를 탐색하며 조건에 맞는 최적해 찾기

 

정리하자면,

조건(잘린 나무 합이 M 이상)에 맞는 절단기 높이 H의 최댓값을 구하는 최적화 문제

-> 높이 H가 주어졌을 때 조건에 부합하는지 아닌지를 판단하는 결정 문제로 바꿔서 여러 번 탐색

 

절단기 높이-가져갈 수 있는 나무 함수는 감소함수이므로 parametric search 가능

 

코드

/*boj s2 2805 나무 자르기*/
#include <iostream>
#define MAXN 1000010
using namespace std;

int N, M;
long long tree[MAXN];

long long cut(long long x) {
    long long sum = 0;

    for (int i = 0; i < N; i++) {
        sum += (tree[i] - x) >= 0 ? (tree[i] - x) : 0;
    }

    return sum;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        cin >> tree[i];

    long long st = 0;
    long long en = 1000000000;

    while (st < en) {
        long long mid = (st + en + 1) / 2;
        long long res = cut(mid);

        if (res < M) // 만족 X, 높이 더 내려가야 함
            en = mid - 1;
        else // 만족 O, 높이 최댓값을 구해야 하므로 값 올리기
            st = mid;
    }

    cout << st << "\n";
}