[백준] 2512번 예산 (python,c++)

https://www.acmicpc.net/problem/2512

2512번: 예산

 

방법이 여러가지 떠올라 고민을 정말 많이 했다. 명료하게 구해야하는것에 집중하자. '배정된 예산들 중 최댓값인 정수를 출력' 해야 한다.  이분탐색을 이용해 정답을 좁혀나간다. 예산이 너무크면 줄이고,너무 작으면 늘린다. (파라메트릭 서치)

 

예산이 맞는지 확인하는 방법은 다음과 같다. 예산요청값vs예산값 비교 후, 예산요청값이 예산값보다 작으면 전자,크면 후자를 배정한 값을 모두 더한다. 이 값이 틀리다면 다시 예산값을 점검하는 과정을 반복한다. 

---

SOLUTION CODE

# PYTHON

N = int(input())
req = list(map(int,input().split()))
M = int(input())

lo = 0
hi = max(req) # 배정된 예산들 중 최댓값인 정수 최댓값(국가 돈 짱많을때)
mid = (lo + hi) // 2
ans = 0

def is_possible(mid):
    return sum(min(r,mid) for r in req) <= M
    
while lo <= hi:
#    print(f'lo: {lo}, mid: {mid}, hi: {hi}, ans: {ans}')
    if is_possible(mid):
        lo = mid + 1
        ans = mid # 가능하면 답 갱신
    else:
        hi = mid - 1
    
    mid = (lo + hi) // 2

print(ans)

 

# C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N,M;
vector<int> req;

int main(){
	cin >> N;
	for(auto i=0; i<N; i++){
		int X;
		cin >> X;
		req.push_back(X);
	}
	cin >> M;
	
	int lo=0;
	int hi = *max_element(req.begin(),req.end());
	int mid = (lo + hi) / 2;
	int ans = 0;
	int sum;
    
	while(lo<=hi){
		sum=0;
		int mid = (lo+hi)/2;
		for(auto i=0; i<N; i++){
			sum += min(req[i],mid);
		}
		if(M>=sum){
			ans=mid;
			lo=mid+1;
		}else{
			hi=mid-1;
		}
	}
	cout<<ans;
}