백준 2805번 : 나무 자르기 (C++) (이분탐색)

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

2805번: 나무 자르기

 

 

 

코드

#include <iostream>
using namespace std;
 
int main() {
    int n;
    long long m,mid,min=0,max=0,ans=0;
    cin>>n>>m;
    long long arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        if(max<arr[i]) max=arr[i];
    }
    
    max--;
    while(min<=max)
    {
        mid=(min+max)/2;
        long long sum=0;
        for(int i=0;i<n;i++)
        {
            sum+=(arr[i]-mid)>=0?arr[i]-mid:0; 
        }
        if(sum<m) max=mid-1;
        else
        {
            if(ans<mid) ans=mid;
            min=mid+1;
        }
    }
    cout<<ans;
    return 0;
}

 

풀이

백준 1654번과 유사한문제이다.

https://zz12345.tistory.com/15

백준 1654번 : 랜선 자르기 (C++) (이분탐색)

 나무를 가장 낮은 높이에서 자를 경우는 0이고 높은 높이에서 자를 경우는 가장 높은 나무의 높이-1이다. 1부터 가장 높은 나무의 높이-1까지를 모두 검사해서 답을 찾는 방법은 시간제한이 초과할 것이라고 생각해서 이분 탐색을 사용했다. 이분 탐색을 수행할 때 각 나무의 높이 - mid 값을 전부 더하여 가져가려는 나무의 높이와 비교하는데 각 나무의 높이 - mid가 마이너스가 된다면 (나무보다 높은 곳에 절단기를 둔다면) 가져가는 나무는 0이 되기 때문에 22행에 삼항연산자를 사용해서 마이너스 값이라면 0으로 바꿔줬다. 각 나무의 높이-mid 값을 전부 더한 값이 가져가려는 높이보다 작다면 max=mid -1을 해주어서 나무를 더 낮은 높이에서 자른다. 나무를 잘랐을 때 가져가려는 나무 높이보다 큰 값이 나온다면 그럴 때 가장 큰 mid 값을 저장하기 위해 27행을 수행하고 더 높게 잘라도 가져가려는 나무보다 큰 값이 나오는지 알아보기 위해 28행에서 min=mid+1을 수행해준다. 이를 min<=max가 true일 때까지 수행한 뒤 ans의 값이 답이다.