[C++][알고리즘] 프로그래머스:: 예산

https://programmers.co.kr/learn/courses/30/lessons/43237

코딩테스트 연습 - 예산 | 프로그래머스

문제 설명

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그래서 정해진 총액 이하에서 
가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다.

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150일 때, 상한액을 127로 잡으면 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 됩니다.
budgetsMreturn[120, 110, 140, 150]485127

나의 코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int solution(vector<int> budgets, int M) {
    long long sum=0;
    sort(budgets.begin(), budgets.end());
    for (int i = 0; i < budgets.size(); i++) {
        sum += budgets[i];
    }
    if (sum < M) return *(budgets.end() - 1);
    long long avg = sum / budgets.size();
    long long sum1 = 0;
    int size = budgets.size();
    long long avg1 = M / size;
    for (int i = 0; i < budgets.size(); i++) {
        if (budgets[i] > avg1) return avg1;
        sum1 += budgets[i];
        size--;
        avg1 = (M - sum1) / size;
    }
}

원리

만약 예산이 400 이고 4개의 지방의 요청액이 [ 10 , 50 , 190 , 220 ] 이라고 하자. (sort함수를 통해 오름차순으로 정렬되어 있음 무조건!)

위의 코드는 다음의 과정을 거친다.

 

0. 먼저 모든 지방에 원하는 예산만큼 지원이 가능한지를 검사한다.

만약 모든 요구 예산액의 합이 정부가 보유한 예산보다 작다면, 당연히 지급가능하다. 문제 표현이 약간 모호한데, 이럴 때는 return 을 지방이 요구하는 예산 중 가장 큰 예산값을 해야한다. < index: end() -1 >

 

1.가장 낮은 예산부터 제공가능한 최대의 예산 배분액보다 작은지를 검사한다.

avg = 400 / 4 = 100, 10보다 100이 크므로 제공 가능.

 

2. 요구 예산액을 지급하고 남은 금액의 최대 예산배분액보다 큰지를, 그 다음 지방에서도 검사한다.

첫번째 지방에 10을 주었으므로 남은건 390. 2,3,4번째 마을엔 아무리 많아야 평균값인 130 이상을 줄 수는 없다.

50 < 130 이므로 50도 지급 가능.

 

3. 만약 avg보다 큰 예산을 요구한다면 그 지점부터는 avg가 상한의 예산이 될 것이다.

400 - 60 = 340 이 남은 예산. 남은 두 지방에는 170씩 지급이 가능하다.

190> 170 이므로 원하는 만큼의 예산을 줄 수는 없기 때문에 170이 지급가능한 최대 예산이다.

[ 10 , 50 , 170 , 170 ] -> 합: 400 이 가장 이상적인 예산 배분액이 되는 것이다.

따라서 return 값 또한 170이 된다. (avg)

 

 

사족

테마가 이분탐색인 문제인데 이분탐색은 하지도 않았다. 여기서 스스로 감점.

이분탐색으로 발견하는 프로세스를 한 번 상상해보도록 하자.

 

효율성테스트2 를 계속 통과하지 못 했다. 그 이유는 지방들이 요구하는 모든 예산들의 합이

integer 표현 범위를 초과할 수 있기 때문이다. 이때문에 sum 의 data type 을 long long 으로 변경하였다.

앞으로 효율성 테스트에 실패한다면 값 표현 범위를 초과하는 변수가 존재하는 지 를 체크해보도록 하자.