백준 2512번 - 예산

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

2512번: 예산

• 필요한 배경지식

이분탐색, 매개 변수 탐색 : parametric search

 

 

• 문제 해결 방법

답으로 출력될 값(배정될 예산)을 기준으로 하여, 매개 변수 탐색을 하면 됩니다.

즉, 이분탐색으로 배정될 예산을 구하는 과정에서 그 예산이 배정될 수 있으면 예산을 늘리고 배정될 수 없다면 줄이면서 가장 큰 값을 찾아나가는 방법입니다.

이분탐색의 구현은 lower bound 방식을 활용하여 구현했습니다.

 

 

• 비슷한 문제

백준 1654번 - 랜선 자르기 : https://www.acmicpc.net/problem/1654

백준 2805번 - 나무 자르기 : https://www.acmicpc.net/problem/2805

백준 2792번 - 보석 상자 : https://www.acmicpc.net/problem/2792

 

 

 

 

• C++ 전체 코드

#include<bits/stdc++.h>
using namespace std;

int N,M;
int m[10001]{};

// 예산(mid)이 총 예산(M)안에 들어올 수 있는지 확인
bool isP(int mid){ 
    int sum = 0;
    for(int i=0; i<N; i++){
        if(m[i] <= mid) sum += m[i];
        else sum += mid;
    }
    if(sum <= M) return true;
    else return false;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>N;
    int l=0,r=0;
    for(int i=0; i<N; i++) {
        cin>>m[i];
        r = max(r, m[i]); // 탐색할 예산의 최댓값
    }
    cin>>M;

    while(l<=r){
    	// mid = 탐색할 예산의 값
        int mid = (l+r)/2;
        if(isP(mid)) l = mid + 1; // 예산이 충분하다면 늘리기
        else         r = mid - 1; // 예산이 충분하지 않다면 줄이기
    }
    cout<<r;
}