백준 2805번, 나무자르기

백준 2805번 c++ 문제풀이

문제:

백준 2805

풀이:

1. 벡터에 나무의 길이를 저장한다.
2. 벡터를 오름차순으로 정렬한다.
3. 0부터 가장 긴 나무 길이 사이에서 이분 탐색을 통해 가장 적절한 길이를 찾는다
4. 가장 짧은 나무부터 이분 탐색을 하는 것이 아닌, 0부터 이분탐색을 하는 이유는 가장 짧은 나무를 잘라야할 수도 있기 때문이다.(주의 해야함)
5. int형보다 숫자가 커질 수 있으므로 표현형을 long long 형을 쓰는 경우가 있다.(주의 하자!)

코드:

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

bool check(int input, vector<long long> v, int k){ //중간값을 전달 후, 이 값으로 잘랐을 떄 가능한지를 보는 함수
    long long total = 0;

    for(int i=0;i<v.size();i++){
        if(v[i] <= input){
            total += 0;
        }else{
            total += (v[i] - input); 
        }
    }

    if(total >= k){
        return true;
    }else{
        return false;
    }
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    vector<long long> v;

    cin >> n >> m;

    for(int i=0;i<n;i++){
        long long input;
        cin >> input;

        v.push_back(input);
    }

    sort(v.begin(), v.end()); //정렬 한다.
    
    int left;
    int right;

    left = 0;
    right = v[n-1];
    int result = 0;
    while(left <= right){ //둘이 같아지거나 left가 더 커질 때까지 반복한다. 
        int mid = (left + right)/2;

        if(check(mid, v, m)){//true면 
            result = mid;  //최댓값 구하기
            left = mid+1; //left를 더 늘려, 미드값을 증가시켜도 된다. 최댓값이 더 있을 수도 있기 때문이다.
        }else{
            right = mid-1; //right값을 줄여, 미드값 감소 시킨다. check 함수를 만족시키지 못했기 떄문이다.
        }
    }

    cout << result;
    return 0;
} 

감사합니다.