[백준] 2512 - 예산 (C++)

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

여러 지방의 예산 요청을 심사해 국가의 예산을 분배해야 한다. 이때, 주어진 방법을 사용해 정해진 총액 이하에서 가능한 한 최대의 총 예산을 배정한다.

1. 모든 요청이 배정될 수 있는 경우, 요청한 금액을 그대로 배정
2. 모든 요청이 배정될 수 없는 경우, 특정한 정수 상한액을 계산해 그 이상인 예산 요청에는 모두 상한액을 배정
   1. 상한액 이하의 예산 요청에는 요청한 금액을 그대로 배정

 

여러 지방의 예산 요청과 국가 예산의 총액이 주어질 때, 위의 조건을 모두 만족하도록 예산을 배정하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 3 ≤ N ≤ 10,000
• 1 ≤ (각 지방의 예산 요청 값) ≤ 100,000
• N ≤ M ≤ 1,000,000,000

 

이분탐색을 사용하지 않는다면 M번마다 10,000번 탐색을 해야하고 M이 최대일 때 시간 초과가 발생한다. 사용한다면 10,000 × log(1,000,000,000)으로 시간 안에 해결할 수 있다.

 

주의할 점은 배정된 예산들 중 최댓값을 구해야 하는 문제이기 때문에 이분탐색 시 종료 조건을 잘 설계해야 한다.

 

비슷한 문제로 2805 - 나무 자르기, 1654 - 랜선 자르기가 있다. 랭크도 실2로 똑같으니까 복습할 겸 풀어보는 것도 좋을 듯하다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N 입력 받기
2. 각 지방의 예산 요청 값 입력 받기 (N개)
3. M 입력 받기
4. 이분탐색을 사용해 조건을 만족하는 모든 mid 값 중 최댓값을 찾기
5. 구한 최댓값 출력

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n,m,x,mx_x,ans;
vector<int> v;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> x;
        v.push_back(x);
        mx_x = max(x,mx_x);
    }
    cin >> m;

    int l=0,r=mx_x+1;
    while (l+1<r) {
        int mid=(l+r)/2, sum=0;

        for (int i=0; i<n; i++)
            sum += (v[i]<=mid ? v[i] : mid);
        
        if (sum>m) {
            r=mid;
        }
        else {
            l=mid;
            ans = max(ans, mid);
        }

    }

    cout << ans;
}