Gidhub BE Developer

[BOJ] 2805. 나무 자르기

2018-09-26
goodGid

Problem

Problem URL : 나무 자르기


[1] Answer Code (18. 09. 26)

#include<iostream>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
ll n,m;
ll ans;
ll arr[1000001];

void b_s(ll l, ll r){
    if( l > r ) {
        ans = r;
        return ;
    }
    ll cnt = 0;
    ll mid = (l+r) >> 1;
    for(int i=0; i<n; i++){
        if(arr[i] - mid > 0 )
            cnt += arr[i] - mid;
    }
    
    if( cnt < m ){
        b_s(l, mid - 1);
    }
    else {
        b_s( mid + 1 , r);
    }
}

int main(){
    cin >> n >> m;
    for (int i=0; i<n; i++)
        scanf("%lld",arr+i);

    sort(arr, arr+n);
    b_s(1,arr[n-1]);
    cout << ans << endl;
    return 0;
}

Review

  • ans를 갱신하는 시기를 left > right 보다 클 경우에 해주면 된다.

  • 탐색을 계속하다 끝나는 시점은 무조건 left과 right이 겹치는 부분이다.

  • 즉 그 때가 최적의 답이다.

  • 아무튼 이 문제의 핵심은 파라메트릭 서치 알고리즘을 사용하는 것이다.

  • 파라메트릭 서치(Parametric Search)에 대해 알아보도록 하자.


Recommend

Index