백준] 5545 - 최고의 피자(JOI 2012 예선)

시간 제한 : 1초

메모리 제한 : 128MB

입력

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

출력

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

소스코드

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int main(void)
{
	int n, a, b, c, d[100], sum, toping, bil;
	double max = 0;
	cin >> n >> a >> b >> c;
	for (int i = 0; i < n; i++)
		cin >> d[i];
	sort(d, d + n, greater<int>());
	bil= a,sum = c, max = (double)c / a;
	for (int i = 0; i < n; i++)
	{
		if ((double)d[i] / b >= max)
			max = (double)((max*bil) + d[i]) / (bil + b), bil += b;
		else
			break;
	}
	cout << (int)max;
}

Tip

그리디로 접근하면 쉽게 풀어낼 수 있다.

달러 당 열량값이 높아 평균값을 올리는 토핑들을 최대한 취하는 방식으로 접근한다. 열량을 기준으로 내림차순 정렬을 했기 때문에 피자의 상태에 따른 달러 당 열량값에 못 미치는 케이스가 발견되면 이후 모든 토핑에 대해서는 조사를 취할 필요가 없으므로 반복문을 탈출한다.