나무 자르기

코드

[ 시간초과 코드 ]

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
ll N,M, ans;
ll MAX;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // N=10^6, M=10^9
    cin >> N >> M;
    priority_queue<int> pq;
    for(int i=0;i<N;i++)
    {
        int a;
        cin >> a;
        pq.push(a);
    }
    ll co=0;
    ll H=pq.top();
    while(true)
    {
        if(pq.empty()){
            ans += co;
            H--;
        }else if(pq.top() < H){
            ll n = (co)*(H-pq.top());
            if(ans + n > M){
                ans += co;
                H--;
            }else{
                ans += n;
                H = pq.top();
            }
        }
        else{
            pq.pop();
            co++;
        }
        if(ans >= M) break;
    }
    cout << H;
}

---

[ 이분탐색 코드 ]

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
ll N,M,high;
vector<ll> arr(1000002);
/* 이진탐색 - O(logN) */
void bs(vector<ll>& arr, ll st, ll en){
    ll ans=0;
    while(st <= en)
    {
        ll tot=0;
        ll mid = (st + en)/2;
        for(auto a : arr)
            if(a > mid)
                tot += a-mid;
        if(tot < M)
            en = mid-1;
        else{
            ans = mid;
            st = mid + 1;
        }
    }
    cout << ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for(int i=0;i<N;i++)
    {
        cin >> arr[i];
        high=max(high,arr[i]);
    }
    bs(arr,0,high);
    return 0;
}

• 로직
  • 나무의 최대 길이를 구한다
  • 이분탐색으로 최적의 나무 높이를 구한다

• 주의
  • 합을 구하는 tot변수는 반드시 long long 혹은 그 이상이어야 한다