Gidhub BE Developer

[BOJ] 2512. 예산

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[10001];

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

int main(){
    cin >> n ;
    for (int i=0; i<n; i++)
        scanf("%lld",arr+i);
    cin >> m;
    
    sort(arr, arr+n);
    b_s(1,arr[n-1]);
    
    cout << ans << endl;
    return 0;
}

Review

  • [1] 부분에서 <=가 아닌 <로 하게 되면 틀리게 된다.
4
10 10 10 10
40 라고 할 때

mid : 10 
sum은 40이 된다.
그러면 
sum == m 같게 되는데 

이 때 
// [1]
if( sum <= m ) 라면
l : mid +1 
r : r

// [2]
if( sum < m ) 라면
l : l
r : mid -1 이 된다.

그런데 위 2가지 상황에서
l과 r은 이미 같은 값이다.

만약 [1]번 로직을 따른다면 
종료 조건 ( l > r )에서 
ans = r = 10이 되지만

[2]번 로직을 따른다면
ans = r = 9가 된다.

그렇기 때문에 [1]번 로직을 따라야한다.
  • ans를 갱신하는 시기를 left > right 보다 클 경우에 해주면 된다.

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

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

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

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


Comments

Content