[algorithm] CodeUp #3321 : 최고의 피자

CodeUp #3321 : 최고의 피자

사용 언어 : c++

<풀이>
조건을 차근히 읽어야 했던 문제 ..!
N가지의 토핑 종류 중에 같은 종류를 2개 이상 올릴 수 없는 조건을 대충 읽고 2개까지 올릴 수 있다고 생각했음..;
N가지의 토핑이 있을 때 토핑을 0개 선택하는 것부터 N가지를 모두 하나씩 담는 모든 경우의 수가 2^N인 것 까지 생각해냈지만 문제를 해결하지는 못했다
문제 구분이 greedy로 되어있는 것에 초점을 맞춰 생각해보니 어차피 모든 토핑의 가격은 같으므로 토핑의 열량을 내림차순으로 정렬해 더해나가면 되는 문제였다 !

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(int a, int b) {
	return a > b;
}
  
int main() {
	int top_kind; //토핑의 종류
	cin >> top_kind;
	int dough_kcal; //도우 열량
	int top_price, dough_price; //토핑 가격, 도우 가격
	double max_kcal; //최고의 피자 

	cin >> dough_price;
	cin >> top_price;
	cin >> dough_kcal;
	int total_kcal = dough_kcal;
	double temp_kcal;

	vector<int> top_kcal(top_kind);

	for (int i = 0; i < top_kind; i++) {
		cin >> top_kcal[i];
	}

	sort(top_kcal.begin(), top_kcal.end(), compare);
	max_kcal = (double)dough_kcal / dough_price; //최고 열량, 도우만

	for (int i = 0; i < top_kcal.size(); i++) {
		total_kcal += top_kcal[i]; //i번째로 큰 수 total_kcal 에 더하기
		temp_kcal = (double)total_kcal / (dough_price + top_price * (i + 1));//열량 계산
		if (max_kcal < temp_kcal) {
			max_kcal = temp_kcal;
		}
	}
	cout << (int)max_kcal << endl;
}