[2512] 예산

 

문제

2512번: 예산

 

---

 

처음엔 코드도 60줄이 넘고 내가 생각하기에도 코드가 너무 복잡한 것 같은데 제출 결과도 계속 틀렸다고 떠서

뭐가 문제일까 생각해봤더니 예외 테스트케이스가 있었다...

이분 탐색 문제였기 때문에 자꾸만 어떤 표본들의 중간값을 찾으려고 했던 탓이다.

예를 들어, 각 지방에서 요청한 예산이 100, 110, 120, 130 이었다면

나는 초기 상한액을 (100+110+120+130) / 4 = 115로 설정하여서

상한액이 115일때 배정된 예산이 국가예산 총액보다 작다면 상한액을 1씩 증가시키고,

그 반대의 경우라면 상한액을 1씩 감소시키도록 만들었다.

하지만 이렇게 되면 런타임에러가 발생하고 정답으로는 130을 출력했어야 했다.

즉, 초기 상한액을 각 지방에서 요청한 예산들의 평균으로 설정하는 것이 아니라 예산들 중 최댓값으로 설정했다면 바로 해결할 수 있는 문제

 

---

 

✍️ 알고리즘

1. 각 지방의 요청예산을 request에 입력받는다.

2. 초기 maximum은 요청 예산 중 최댓값으로 설정한다.

3. 배정 예산을 구하고 이 값이 국가예산 총액보다 작다면 maximum값을 크게 해줘도 배정 예산은 국가예산 총액보다 작으므로

그냥 maximum을 리턴하고 끝낸다.

4. 배정 예산이 국가예산 총액보다 크다면 maximum을 1만큼 감소시키고 다시 배정 예산을 구하고 위의 과정을 반복한다.

 

🔎 해결 방법

각 지방의 예산 요청이 위와 같고  총 예산은 10이라고 하자.

max = 배정된 예산들 중 최댓값(=5)

sum = 그 때의 각 지방에 배정된 예산들의 총 합

total = 총 예산(=10)

이라고 하면 max 는 각 지방에서 요청한 예산들 중 최댓값으로 초기화해준다.

이때 sum은 16이고 이 값은 total 보다 크므로 최대 배정 예산을 1만큼 감소시킨다.

최대 배정 예산이 4일때의 sum은 14이고, 이 값 역시 total 보다 크므로 최대 배정 예산을 1만큼 감소시킨다.

 

최대 배정 예산이 3일때의 sum은 11이고, 이 값 역시 total 보다 크므로 최대 배정 예산을 1만큼 감소시킨다.

 

최대 배정 예산이 2일때의 sum은 8이고, 이 값은 total보다 작거나 같으므로 2를 출력하고 프로그램을 종료하면 된다!

 

💡 내 코드(C++)

// [2512] 예산
// https://www.acmicpc.net/problem/2512

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

int start(int , int, int);
vector <int> request; // 각 지방의 예산요청 금액

int main(void)
{
    int n, money; // 지방의 수
    int max = 0, total = 0; // 상한액, 국가예산 총액
    cin >> n;
    for(int i = 0 ; i < n ; i++) {
        cin >> money;
        request.push_back(money);
    }
    cin >> total;
    sort(request.begin(), request.end());
    max = request[n-1]; // !!최초 상한액은 지방 예산요청 중 최댓값으로 설정!!
    cout << start(n, max, total) << endl;
}

int start(int n, int max, int total)
{
    int sum;
    while(true) {
        sum = 0;
        for(int i = 0 ; i < n ; i++) {
            sum += (max > request[i] ? request[i] : max);
        }
        if(sum <= total) {
            return max;
        }
        else {
            max--;
        }
    }
    return max;
}