문제
상근이는 근처 피자 가게에서 매일 저녁으로 피자를 배달해 먹는다. 주머니 사정이 얇아진 상근이는 이번 달부터는 "최고의 피자"를 구매하려고 한다. 최고의 피자란, 피자 가게에서 주문할 수 있는 피자 중 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원 당 열량을 계산해보면 지속적으로 값이 증가하다가 감소하는 양상을 확인할 수 있다. 따라서 for문을 사용하여 탐색을 하되 값이 감소하는 구간에서 탐색을 중지하고 답으로 채택한다.
회고
HCPC출제 건으로 양치기를 좀 해야해서 브론즈만 푸는데 브론즈 문제를 벨로그에 일일히 올리기는 좀 그래서 안올렸다. 출제 요건이 1000문제였기 때문이다. 브론즈 문제는 푸는데 얼마 걸리지도 않고, 가끔 하루에 약 30문제 가량을 풀다 보니 이걸 일일히 올리기엔 마음에 걸려서 풀기만 하고 벨로그에 올리진 않았다. 뭐 그래도 이제 50문제 정도 남았으니까 다른 티어들도 슬슬 다시 풀어보자..ㅎㅎ
코드
from math import floor
n = int(input())
dough, topping = map(int, input().split())
dough_calorie = int(input())
ls = [0] + sorted([int(input()) for _ in range(n)], reverse=True)
maximum_value = 0
total = dough_calorie
for i, e in enumerate(ls):
total += e
value = total / (dough + topping * i)
if value > maximum_value:
maximum_value = value
else:
break
print(floor(maximum_value))
