[BOJ] 백준 2805 나무 자르기

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

Binary Search (이분 탐색) 

Binary Search (이분 탐색)

[탐색] Parametric Search 

[탐색] Parametric Search

아래와 같이 4개의 나무가 존재할 때 특정 높이(H)로 잘라서 그 윗부분을 상근이가 들고갑니다.

만약 아래와 같이 자른다고 가정했을 때,

필요한 나무보다 많은 양을 가져갈 수는 있지만 낭비되는 부분이 있으며 환경이 좋지 않습니다.

필요한 나무를 구할 수 있는 최적의 높이(높이의 최대값)을 이분탐색을 이용해 구합니다.

(Upper Bound)

---

#pragma warning (disable : 4996)
#include <stdio.h>
 
inline int max(int A, int B) { if (A > B) return A; return B;}
const int LM = ((int)1e6 + 10);
int N, need;
int treeHeight[LM];
 
void input() {
    scanf("%d %d", &N, &need);
    for (int i = 0; i < N; ++i) {
        scanf("%d", treeHeight + i);
    }
}
 
int isPossible(int m) {
    int sum = need;
    for (int i = 0; i < N; i++) {
        // 자르는 높이 > 나무 높이인 경우
        if (treeHeight[i] <= m)
            continue;
        sum -= treeHeight[i] - m;
        // 필요한 길이를 만족
        if (sum <= 0) return 1; 
    }
    return 0;
}
 
int solve() {
    int start = 0, end = 0, mid, sol = 0;
    for (int i = 0; i < N; i++) {
        // 제일 나무 높이가 자르는 높이의 최대로 초기 설정
        end = max(end, treeHeight[i]);
    }
 
    while (start <= end) {//upper bound찾기 (제한 높이가 낮을수록 더 많은 나무를 얻을수 있음)
        mid = (start + end) / 2;
        if (isPossible(mid)) {
            sol = mid; start = mid + 1;
        }
        else end = mid - 1;
    }
    return sol;
}
 
int main() {
    input();
    printf("%d\n", solve());
}