[백준 5545번] 최고의 피자 (C++)

문제링크 : https://www.acmicpc.net/problem/5545

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N, A, B, C; //토핑 갯수, 도우 가격, 토핑 가격, 도우 열량
int arr[10001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> A >> B >> C;
    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }

    sort(arr, arr+N, greater<>()); //토핑 열량이 높은 순서대로 비교

    int result = C/A; //1원당 열량 (최고)

    for(int i=0; i<N; i++)
    {
        result = max(result, (C+=arr[i])/(A+=B));
    }
    
    cout << result;
    
    return 0;
}

 

토핑 열량이 높은 순서대로 비교하기 위해 입력받은 토핑을 내림차순으로 정렬해준다.

초기값으로 1원당 열량 값 (토핑이 없을 때의 값) 을 설정해준다.

 

이후 새롭게 열량과 가격을 추가해가며 1원당 열량 값을 갱신하고, 이렇게 갱신한 값 중 가장 큰 값을 출력한다.