2805 - 나무 자르기 - 이분 탐색

문제

문제링크 : https://www.acmicpc.net/problem/2805

풀이전략

1. 나무를 몇미터에서 자를지가 중요하다. 하지만 나무의 개수는 1000000으로 N^2으로 해결하면 문제를 풀 수 없다. 따라서 NlogN으로 만들기 위해 이분 탐색을 사용한다.
2. M은 2,000,000,000 이고 N은 1,000,000이다. 따라서 int형으로는 나무의 높이의 합을 계산할 때 부족할 수 있다. 따라서 long long을 사용해주어야한다.
3. 먼저 높이를 선정하고, 그 높이로 나무들로부터 총 얼마를 얻을 수 있나를 계산한다. 나무들로부터 얻을 수 있는 값이 목표치보다 작을 경우 자를 높이를 낮춰주고 그 반대의 경우 자를 높이를 높여주면 된다.

코드

#include<bits/stdc++.h>

using namespace std;

// 틀린이유 1 long long 으로 선언해주는 것을 생각하지 못함

int N, M;
vector<int> arr;
int res;
int resVal = 2147000000;
long long getSum(int num){
    long long sum = 0;
    for(int i=1; i<=N; i++){
        if(arr[i] > num){
            sum += arr[i]-num;
        }
    }
    return sum;
}

int BinarySearch(int lt, int rt){
    if(lt>rt){
        return res;
    }
    else{
        int mid = (lt+rt) / 2;
        long long ret = getSum(mid);
        if(ret == M){
            return mid;
        }
        else if(ret > M){
            if(resVal > ret){
                res = mid;
            }
            return BinarySearch(mid+1, rt);
        }
        else{
            return BinarySearch(lt, mid-1);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    freopen("../input.txt","rt",stdin);
    cin >> N >> M;
    int tmp;
    arr.push_back(0);
    for(int i=1; i<=N; i++){
        cin >> tmp;
        arr.push_back(tmp);
        
    }
    sort(arr.begin(), arr.end());
    /// 두번째 틀린이유 아무생각없이 arr[1]을 넣었음 모든 나무의 크기도 같을수 있음을 생각했어야한다. 
    cout<<BinarySearch(1, arr[N])<<endl;
    // cout<<BinarySearch(arr[1], arr[N])<<endl;
    return 0;
}

소감

문제를 한번에 풀지 못하였는데 그 이유는 먼저 long long으로 값을 선언해 주지 않아서이다. 또한 모든 나무도 같은 값을 가질 수 있으므로 아무생각없이 가장 작은 값을 lt로 넣어주는 것이 아니라 1을 넣어주어야한다.

반드시 int형을 벗어나면 long long으로 선언해주어야한다.