백준 5545. 최고의 피자

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

5545번: 최고의 피자

 

토핑의 칼로리를 내림차순으로 정렬하고 칼로리가 높은 토핑부터 하나씩 더해가며 1원당 열량이 높은 값을 갱신한다.

주의할점은 토핑을 하나도 선택하지 않을수도 있다.

 

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

int n, doughPrize, toppingPrize, doughCal;
int toppingCal[10010];

int main()
{
    cin >> n >> doughPrize >> toppingPrize >> doughCal;
    for(int i = 0; i < n; i++)
        cin >> toppingCal[i];

    sort(toppingCal, toppingCal+n, greater<>());

    int cal = doughCal;
    int prize = doughPrize;
    // 토핑을 전혀 선택하지 않는 경우
    int ans = doughCal / doughPrize;
    for(int i = 0; i < n; i++)
    {
        cal += toppingCal[i];
        prize += toppingPrize;

        ans = max(ans, cal/prize);
    }

    cout << ans;
}