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)에 대해 알아보도록 하자.