최고의 피자
상근이는 근처 피자 가게에서 매일 저녁으로 피자를 배달해 먹는다. 주머니 사정이 얇아진 상근이는 이번 달부터는 "최고의 피자"를 구매하려고 한다. 최고의 피자란, 피자 가게에서 주문할 수 있는 피자 중 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달러당 칼로리를 측정할 수 있습니다. 여기서, 토핑이 추가된다고 하면 피자 전체의 칼로리는 증가하지만, 가격도 증가하기 때문에 토핑을 추가할 때 주의해야 합니다.
토핑의 칼로리가 높은 순서부터 토핑을 정렬해서 피자에 하나씩 추가해가면서 기존의 1달러당 칼로리와 비교하여 더 높다면 가격과 칼로리의 토핑의 가격과 토핑의 칼로리를 추가해가는 형식인
그리디 알고리즘을 이용해서 해결할 수 있습니다. 다만, 정답은 소수점 이하는 생략해야 하므로, math라이브러리의 floor함수를 이용하면 됩니다.
import sys
import math
input = sys.stdin.readline
n = int(input())
a, b = map(int, input().split())
c = int(input())
d = []
for _ in range(n):
d.append(int(input()))
toppings = sorted(d, reverse=True)
price = a
total_kcal = c
result = c / a
for topping in toppings:
tmp = (total_kcal+topping) / (price+b)
if result < tmp:
result = tmp
total_kcal += topping
price += b
print(math.floor(result))
