백준 2805 나무자르기 c++ [컴공과고씨]

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

2805번: 나무 자르기

일단 이 문제의 경우 이분 탐색을 사용하였다.

절단기를 높게 설정하면 잘리는 나무는 적어진다. 절단기를 낮게 설정하면 잘리는 나무는 커진다. 

절단기 설정 높이를 이분탐색을 사용하여 구하면 된다.

 

low는 0, high는 나무 길이의 최대값인 1,000,000으로 설정하고 이분탐색을 시작한다.

절단기의 설정 높이가 모든 나무길이보다 크게되면 의미가 없기 때문.

설정된 절단기 높이를 이용하여 나무를 잘라 잘린 길이를 저장한다. 

 

만약 내가 가져가려는 길이와 절단기 설정 길이가 같다면 최대 높이로 설정한 것이므로 

답을 저장하고 break를 걸어 주었다.

 

가져가려는 나무 길이보다 잘린 나무 길이가 더 크다면 답이 될 수 있기 때문에 첫번째 조건문을 걸어주고

그 다음 조건문은 설정 길이를 최대를 해주기 위해서 걸어주었다.

이 때 low는 잘린 나무 길이가 가져가려는 길이보다 크기 때문에 그 다음 탐색해야하는 절단기 설정 높이는

이 전 보다 더 높게 설정을 해야 나무가 덜 잘리기 때문에 mid+1을 해준다.

 

잘린 나무 길이가 가져가려는 길이보다 작을 때에는 절단기 설정을 더 작게 만들어 더 많은 나무를 자르기 위해서 

high = mid -1을 해준다.

 

이렇게 하면 끝. 전체 코드는 밑에 !

#include <iostream>
using namespace std;
 
int main(){
    int n, m;
    cin >> n >> m;
    long long* tree = new long long[n]; // 더 많은 배열 할당을 위한 동적할당
    for (int i = 0; i < n;i++){
        cin >> tree[i];
    }
 
    long long high = 1000000000;
    long long low = 0;
    long long mid;
    long long cut_tree;
    long long ans = 0;
    while(low <= high){
        mid = (low + high) / 2;
        cut_tree = 0;
        for (int i = 0; i < n; i++){ 
            if(tree[i] > mid){
                cut_tree = cut_tree + (tree[i] - mid);
            } // 절단기 기준이 나무 길이 보다 작아야 잘림.
        }
        if(cut_tree == m){
            ans = mid;
            break;
        } //잘린 나무길이가 가져가려는 길이와 같으면 답이기 때문에 break.
        else if(cut_tree > m){     
            if(ans < mid){
                ans = mid;
            } // 나무길이를 최소화 하려면 절단기의 설정 길이를 최대로 하기 위한 조건
            low = mid + 1;
        }
        else if(cut_tree < m){
            high = mid - 1;
        }
    } //이분 탐색 활용
    cout << ans;
    delete[] tree; //동적할당 해제
    return 0;
}

yea!