[백준 2805번] 나무자르기 풀이

2805번: 나무 자르기

 

상근이가 자를 수 있는 나무의 개수 N, 상근이가 최소로 가져가야 하는 나무의 길이 M 이 주어졌을 때, 톱날의 최대 높이를 출력하는 문제이다. 주어진 조건들을 수식으로 표현해 보면,

 

N개의 나무 높이를 H1, H2, H3, ..., HN으로, 톱날의 높이를 X로 나타내었을 때,

상근이가 가져가게 될 나무의 높이 = (H1-X)+(H2-X)+(H3-X)+ ... + (HN-X)이고, 이는 M보다 크거나 같아야 한다.

따라서 톱날의 높이의 범위인 1 ~ 1000000000 중에서 조건 (H1-X)+(H2-X)+(H3-X)+ ... + (HN-X)>=M 을 만족하는 X의 최댓값을 구해야 한다. 

 

0 ~ 1000000000 까지 정렬된 수 중, 조건을 만족하는 최댓값을 구하기 위해서 이분탐색법을 사용한다.

먼저, 탐색 범위의 시작 위치(first)를 1, 탐색 범위의 마지막 위치(last)를 1000000000 설정한다. 이분 탐색 알고리즘은 탐색 범위를 반씩 줄여가는 알고리즘이다. 따라서 first와 last의 중앙값 mid = (first+last)/2 가 톱의 높이 일 때 조건을 만족하는지 검사한다.

 

나무의 높이 H1, H2, ..., HN이 저장된 벡터 v를 순회하면서, (나무의 높이-톱의 높이)인 (v[i]-mid)를 모두 더해 상근이가 가져갈 수 있는 나무의 길이를 구한다. 이때 나무의 높이 보다 톱의 높이가 크거나 같은 경우 상근이가 가져가는 나무는 없으므로 (v[i] > mid)일 경우에만 해당 길이를 더해준다.

 

톱의 높이가 mid일 때, sum(상근이가 가져갈 수 있는 나무의 길이)가 M(가져가야 하는 최소의 길이) 보다 크거나 같다면, 톱의 높이를 mid 이하로 설정하였을 때는 최소 M 이상은 가져갈 수 있게 되어 모두 조건을 만족한다. 하지만 문제에서 요구하는 것은 그 중에서도 최대 높이 이므로 변수 re에 mid를 저장하고 탐색범위의 시작 위치를 first=mid+1로 저장하여 mid 이후의 값들 중 조건을 만족하는 수가 있는지 계속해서 탐색한다.

 

만약 톱의 높이가 mid일 때 sum < M이라면, 톱의 높이를 mid 이상으로 설정하였을 때는 모두 M보다 작은 나무 길이를 가져가게 되며,  이를 탐색 범위에서 제외하기 위해 탐색 범위의 끝 위치를 last=mid-1로 조정한다.

 

이렇게 first <= last 일 때까지 반복하여 first와 last를 이동시키면, 변수 re에는 조건을 만족하는 최대 톱의 높이가 저장된다.

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
using namespace std;

int BinarySearch(const vector<int> &v, int M) {

    int first = 1;
    int last = 1000000000;
    int mid;
    int re = 0;

    while (first <= last) {
        
        mid = (first+last)/2;
    
        long long sum = 0;
        for (int i=0; i<v.size(); i++) {
            if (v[i] <= mid) continue;
            sum+=(v[i]-mid);
        }

        if (sum >= M) {
            re = mid;
            first = mid+1;
        }
        else last = mid-1;
    }
    return re;
}

int main() {

    int N, M;
    scanf("%d %d", &N, &M);

    vector<int> v(N);
    for (int i=0; i<N; i++)
        scanf("%d", &v[i]);

    int maxCutPoint = BinarySearch(v, M);
    printf("%d\n", maxCutPoint);
    return 0;
}