(C++) - 백준(BOJ) 2805번 : 나무 자르기

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

2805번: 나무 자르기

이분탐색(Binary Search) 문제입니다.

 

풀이방법

 1. 나무길이의 정보를 배열에 입력받고 오름차순으로 정렬합니다.

 

 2. 찾으려는 절단기의 높이를 mid로 정해 이분탐색을 시행합니다. O(100만log100만)으로 시간제한에 걸리지 않습니다.

자른 나무들의 합이 m보다 작다면 다많이 잘라야하므로 절단기의 높이를 낮춰야합니다. 그 반대의 경우 절단기의 높이를 높여야 합니다. 절단기 높이의 최대값이므로 right를 반환해줍니다.

 

* 절단기로 잘라 얻을 수 있는 나무들의 합이 int범위를 초과할 수 있습니다.

 

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int treeNum, collectLength;
ll treeInfo[1000001];

ll binarySearch(){
    ll left = 0;
    ll right = 4000000000;
    while(left <= right){
        ll mid = (left + right) / 2;
        ll sum = 0;
        for(int i = 0; i < treeNum; i++){
            if(treeInfo[i] > mid) sum += treeInfo[i] - mid;
        }
        if(sum < collectLength) right = mid - 1;
        else left = mid + 1;
    }
    return right;
}

int main(){
    cin >> treeNum >> collectLength;
    for(int i = 0; i < treeNum; i++) cin >> treeInfo[i];
    sort(treeInfo,treeInfo + treeNum);
    cout << binarySearch();
}