[프로그래머스] 예산

예산

---

1. 이해하기

• 정해진 총액 이하에서 가능한 한 최대의 총 예산을 배정한다.
  • 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
  • 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산 요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.
• 이분탐색 문제이다.

---

2. 구현하기

• 이분탐색을 하기 위해서 요청중 가장 큰 금액을 찾아서 그 금액과 제일 낮은 금액인 1을 비교한다.

  • 상한액을 만들고 이에 맞춰 예산을 계산해본다.
  • 총액과 비교하고 작으면 낮은 금액을 중간 값+1으로, 크면 큰 금액을 중간 값-1으로 바꿔 다시 계산한다.

  long long l = 1, r = 0;
  for(int i = 0; i < budgets.size(); i++)
      if(r < budgets[i]) r = budgets[i];
  long long ans = 0;
  while(l <= r) {
      long long mid = (l+r)/2;
      long long sum = 0;
      for(int i = 0; i < budgets.size(); i++) {
          if(budgets[i] <= mid) sum+=budgets[i];
          else sum+=mid;
      }
      if(sum < M) {
          if(ans < mid) ans = mid;
          l = mid+1;
      }
      else r = mid-1;
  }

---

3. 전체코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> budgets, int M) {
    int answer = 0;
    long long l = 1, r = 0;
    for(int i = 0; i < budgets.size(); i++)
        if(r < budgets[i]) r = budgets[i];
    long long ans = 0;
    while(l <= r) {
        long long mid = (l+r)/2;
        long long sum = 0;
        for(int i = 0; i < budgets.size(); i++) {
            if(budgets[i] <= mid) sum+=budgets[i];
            else sum+=mid;
        }
        if(sum < M) {
            if(ans < mid) ans = mid;
            l = mid+1;
        }
        else r = mid-1;
    }
    return ans;
}