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

문제

상근이는 근처 피자 가게에서 매일 저녁으로 피자를 배달해 먹는다. 주머니 사정이 얇아진 상근이는 이번 달부터는 "최고의 피자"를 구매하려고 한다. 최고의 피자란, 피자 가게에서 주문할 수 있는 피자 중 1원당 열량이 가장 높은 피자를 말한다. 최고의 피자는 여러 종류가 있을 수도 있다.

이 피자 가게는 토핑 N개에서 여러 종류를 선택해서 주문할 수 있다. 같은 종류의 토핑을 2개 이상 선택할 수는 없다. 또, 토핑을 전혀 선택하지 않을 수도 있다.

선택한 토핑은 도우 위에 올라간다. 도우의 가격은 A원이고, 토핑의 가격은 모두 B원이다. 피자의 가격은 도우와 토핑의 가격의 합계가 된다. 즉, 토핑을 k종류 (0 ≤ k ≤ N) 선택했다면, 피자의 가격은 A + B*k원이 된다. 피자의 열량은 도우와 토핑의 열량의 합이다.

도우의 가격, 토핑의 가격, 그리고 도우와 각 토핑의 열량 값이 주어졌을 때, 최고의 피자의 1원 당 열량을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 토핑의 종류의 수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 도우의 가격 A와 토핑의 가격 B가 주어진다. (1 ≤ A, B ≤ 1000) 셋째 줄에는 도우의 열량 C가 주어진다. (1 ≤ C ≤ 10000) 다음 줄부터 N개 줄에는 각 토핑의 열량 Di가 한 줄에 하나씩 주어진다. (1 ≤ Di ≤ 10000)

출력

첫째 줄에 최고의 피자의 1원 당 열량을 출력한다. 소수점 이하는 버리고 정수 값으로 출력한다.

예제 입출력

• 예제 입력 1

3
12 2
200
50
300
100

• 예제 출력 1

37

• 예제 입력 2

4
20 3
900
300
100
400
1300

• 예제 출력 2

100

Solution

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

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

    int N, A, B, C;
    cin >> N >> A >> B >> C;
    vector<int> topping(N);
    for(int i = 0; i < N; i++) cin >> topping[i];
    sort(topping.begin(), topping.end(), greater<int>());
    
    int sumOfcal = C;
    double answer = C / A;

    for(int i = 0; i < N; i++){
        sumOfcal += topping[i];
        int amount = A + B * (i+1);
        double cal_per_amount = (double)sumOfcal / (double)amount;
        answer = max(answer, cal_per_amount);
    }
    cout << floor(answer) << '\n';
}

일단 계산을 하기 전에 하나 고려해야 할 게 있다.
도우가 필수긴 하지만 도우만 집어넣는 게 원당 칼로리가 더 높을수도 있다는 것.

sort(topping.begin(), topping.end(), greater<int>());

토핑들 칼로리 정보를 모두 입력받은 후 내림차순으로 정렬한다. 큰 놈부터 더해봐야 유리할테니까.

int sumOfcal = C;
double answer = C / A;

for(int i = 0; i < N; i++){
    sumOfcal += topping[i];
    int amount = A + B * (i+1);
    double cal_per_amount = (double)sumOfcal / (double)amount;
    answer = max(answer, cal_per_amount);
}
 cout << floor(answer) << '\n';

전체 칼로리 합을 초깃값 C, 1원당 칼로리 초기값을 C/A(도우) 만 잡고 내림차순으로 정렬 된 토핑들을 하나하나 더하면서 계산해본다. 전체 비용 계산은 뭐 어렵지 않다. 혹시 몰라서 double 형으로 값을 계산하고 최종 출력에 floor 함수로 버림 처리를 했는데 그냥 int로 해도 별 문제는 없지 않을까?

그렇다 아무 상관없다.