BOJ 2512 - 예산

www.acmicpc.net/problem/2512

2512번: 예산

 

이분 탐색을 이용해서 풀어야 하는 문제로,

유사한 문제로는 BOJ 1654 랜선 자르기, BOJ 2805 나무 자르기 등 이 있다

 

위 세문제는, 이분 탐색의 시작점과 끝점이라 할 수 있는 start(low), end(high) 를 일종의 인덱스 값으로 잡고

문제에서 요구하는 연산을 수행한 결과를 가지고 주어진 상한선 M 에 가장 가까이 가는 값을 잡아서 도출해야한다

 

이 예산 문제에서는 각 지방의 예산 요청을 받아서 그 중 가장 큰 값을 이분 탐색의 끝 인덱스(end) 로 지정해서 이분탐색을 수행한다. 이분 탐색의 시작 인덱스(start) 는 0 으로 시작한다

그리고 입력 받은 각 지방의 요청 예산 (vec_budget[i]) 역시 이분 탐색의 인덱스 역할을 한다

지불 가능한 예산의 최대 액수를 넘지 않는 값을 찾아야 하므로 min 함수를 사용해서 최소 값을 다 더하여 temp 변수를 만들어낸다

그리고 temp 변수와 전체 예산 한도액 m 과 비교를 통해 이분 탐색의 이동방향을 결정한다.

 

- c++

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
int N;
ll M;
vector<int> vec_budget;
 
void bs(int start, int end, ll m) {
    // start 는 예산액의 최저점, end 는 예산액의 최고점, m 은 예산의 배정가능한 예산의 최댓값이다.
    int result;
    while (start <= end) {
        int mid = (start + end) / 2;  // mid 는 예산액의 상한선을 의미함.
        ll temp = 0;                  // temp 는 예산의 상한선을 이용해서 얻은 지방 예산의 총합
        for (int i = 0; i < N; i++) {
            temp += min(vec_budget[i], mid);  // 지방 요청 예산과 예산 예상의 중간지점 간 최소 값을 찾아서 더함
        }
        if (temp <= m) {
            start = mid + 1;
            result = mid;
        } else {
            end = mid - 1;
        }
    }
    cout << result << '\n';
    return;
}
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
 
    cin >> N;
    int max_budget = 0;
    for (int i = 0; i < N; i++) {
        ll budget;
        cin >> budget;
        vec_budget.push_back(budget);
        max_budget = max(max_budget, vec_budget[i]);
        // 요청한 지방 예산중 가장 큰 값을 end 값으로 지정
    }
 
    cin >> M;
    bs(0, max_budget, M);  // 시작은 0 부터 해서 max_budget 까지 이분탐색
    return 0;
}

 

 

 

 

 

- 참고 (이분 탐색에 대한 설명이 아주 잘 되어 있음, 다른 알고리즘도)

m.blog.naver.com/kks227/220777333252

이분 탐색(Binary Search) (수정 2019-02-15)