BOJ 2805번 나무 자르기

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

github : https://github.com/junho0956/Algorithm/blob/master/2805/2805/%EC%86%8C%EC%8A%A4.cpp

 

설명은 코드에 있습니다.

** 가장 중요한 문제의 핵심은 적어도 M 미터를 가져갈 수 있는 절단기의 높이를 최대로 만들어 주는 것입니다.

** 그래야 최소한의 나무 손실을 막으면서 원하는 만큼 가져갈 수 있습니다.

 

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int N;
    long long M, len, cnt, height = 0;
    vector<long long> v;
    long long left = 0, right = INT_MAX;
 
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> len;
        v.push_back(len);
    }
 
    while (left <= right) {
        long long mid = (left + right) / 2;
        cnt = 0;
        for (int i = 0; i < N; i++) if (v[i] >= mid) cnt += v[i] - mid;
 
        // cnt 가 M 보다 작다는 것은 절단기의 높이가 크다는 것을 의미 => 절단기의 높이를 낮춰야함
        if (cnt < M) right = mid - 1;
        // cnt 가 M 보다 크다는 것은 절단기의 높이가 작다는 것을 의미 => 절단기의 높이를 높여야함d
        else if (cnt > M) {
            left = mid + 1;
            // 적어도 M 미터를 넘게 가져갈 수 있긴 하니 현재 절단기 높이가 height 보다 크다면 갱신
            height = height < mid ? mid : height;
        }
        // 현재 cnt 가 M 미터를 정확히 가져갈 수 있다면 최적의 해
        else {
            height = mid;
            break;
        }
    }
 
    cout << height;
    return 0;
}