[Python] 백준/BOJ 5545번: 최고의 피자 (Silver 3)

💻 Problem

문제 보러 가기

 

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

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

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

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

 

💡 Approach

최고의 피자란 1원당 열량이 가장 높은 피자이다.

1원당 열량은 열량 ÷ 가격이므로 열량은 높을수록, 가격은 낮을수록 1원당 열량이 커진다.

모든 토핑의 가격은 동일하므로 열량이 높은 토핑부터 담아야 유리한 것이다.

 

먼저 토핑을 아예 담지 않고 도우만 계산했을 때의 값을 저장한다.

그 후, 제일 열량 높은 토핑 1개 담았을 때, 제일 열량 높은 토핑 2개 담았을 때, ...

이런 식으로 토핑의 개수를 늘려보면서 1원당 열량이 가장 높을 때를 기록하면 된다.

 

✏️ Solution

import sys
input = sys.stdin.readline

N = int(input()) # 토핑의 종류의 수
A, B = map(int, input().split()) # 도우의 가격, 토핑의 가격
C = int(input()) # 도우의 열량
D = sorted(list(int(input()) for _ in range(N)), reverse=True) # 각 토핑의 열량

price = A # 총 가격
cal = C # 총 열량
best = cal // price # 최고의 피자의 1원당 열량

# 최고의 피자: 1원당 열량이 가장 높은 피자
for i in range(N):
    price += B
    cal += D[i]
    best = max(best, cal // price)

print(best)