[백준 5545] 최고의 피자

www.acmicpc.net/problem/5545

5545번: 최고의 피자

그리디를 사용하는 문제이다. 

피자 1원당 최고의 열량을 찍고 내려오는 지점을 찾는 문제이다.

 

최고점을 찾아야 하므로 이전 열량/가격과 현재의 열량/가격을 비교해서 같거나 크면 업데이트, 작으면 함수를 끝낸다.

**주의: 같을 때도 끝내지 않고 계속 진행해야 한다!

 

피자 가격은 동일하므로 열량을 내림차순으로 정렬한다. 높은 -> 낮은 열량 수준으로 더해서 확인한다.

 

#include <stdio.h>
#include <algorithm>

using namespace std;
int n, a, b, c, d;
int arr[100];
int main(void)
{
  scanf("%d%d%d%d", &n, &a, &b, &c);

  for (int i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }

  sort(arr, arr + n);

  int kcal = c, price = a;
  int best = kcal / price;
  for (int i = n - 1; i > -1; i--)
  {
    int after = (kcal + arr[i]) / (price + b);
    if (best <= after)
    {
      kcal += arr[i];
      price += b;
      best = after;
    }
    else
    {
      break;
    }
  }
  printf("%d\n", best);
  return 0;
}