문제 2805.나무 자르기 (대학생 심화반 2번)

문제 요약 설명

일렬로 세워진 나무들이 있다.

각 나무들은 높이가 제각각이며, 해당 나무들을 높이 H 이상인 부분들만 잘라 길이 M 이상의 나무를 얻으려고 한다. 

M 이상의 나무를 얻을 수 있는 H의 최대값을 구하는 프로그램을 작성하시오.

나무를 얻는 방식 설명

 

입력

첫째 줄에 나무의 수 N과 얻고자 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

 

입력 예제

4 7
20 15 10 17

 

Tips

1. 나무의 수가 최대 100만개나 되고, 가능한 나무의 높이가 매우 높기 때문에 선형적인 탐색으로 찾기는 어렵기에 이진 탐색을 사용해야 한다.
2. 얻는 나무의 길이가 M과 가까운 것이 아닌, M보다 크거나 같아야 하므로 항상 M보다 적게 잘리는 구간은 제외해야한다.

정답 코드

#include <bits/stdc++.h>

#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int main() {
	fastio;
    int N, M; cin >> N >> M;

    vector<int> v1(N+1);
    for(int i = 0; i < N; i++){
        cin >> v1[i];
    }
    
    int min_H = 0;
    int max_H = *max_element(v1.begin(), v1.end());
    int H = (min_H + max_H)/2;
    long long best_M = LLONG_MAX;
    int best_H = H;

    while(min_H <= max_H){
        long long curr_M = 0;
        for(int i = 0; i < N; i++){
            curr_M += (v1[i] - H) > 0 ? v1[i] - H : 0;
        }

        if(curr_M > M){             // 통나무가 초과로 잘린 경우
            min_H = H + 1;
            if(best_M - M > curr_M - M){
                best_M = curr_M;
                best_H = H;
            }
        }
        else if(curr_M < M){        // 통나무가 미만으로 잘린 경우
            max_H = H - 1;
        }
        else{
            best_H = H;
            break;
        }

        H = (min_H + max_H)/2;
    }

    int ans = best_H;

    cout << ans << '\n';
}

 

참고

해당 문제에 쓰인 이진 탐색의 작동 방식을 좀 더 알아보고 싶다면 이진 탐색 글을 찾아서 읽어보자!