BOJ 5545 - 최고의 피자

문제

도우와 토핑으로 피자를 만들 때, 칼로리/가격 비율이 최대인 피자를 구하라. 도우는 필수이고 토핑은 0개 이상 선택 가능하다.

입력

토핑 종류 수 N, 도우 가격 A, 토핑 가격 B, 도우 칼로리 C, 각 토핑의 칼로리가 주어진다.

출력

최대 칼로리/가격 비율(정수 내림)을 출력한다.

예제

입력	출력
`3` `12 2` `200` `100` `50` `200`	`37`

풀이

칼로리가 높은 토핑부터 추가하며 비율이 개선되는 한 계속한다.

토핑을 칼로리 내림차순으로 정렬한다
도우만으로 시작하여 비율을 계산한다
토핑을 하나씩 추가하며 비율이 이전보다 좋으면 갱신한다

핵심 아이디어: 토핑 가격이 동일하므로, 칼로리 높은 순으로 추가하면 비율이 단조 감소하기 시작하는 지점까지가 최적이다.

코드

import sys
 
input = sys.stdin.readline
 
N = int(input())
A, B = map(int, input().split())
C = int(input())
toppings = [int(input()) for _ in range(N)]
 
total_cal = C
total_price = A
best_ratio = total_cal // total_price
 
toppings.sort(reverse=True)
 
for i in range(N):
    total_cal += toppings[i]
    total_price += B
    current_ratio = total_cal // total_price
    if current_ratio > best_ratio:
        best_ratio = current_ratio
 
print(best_ratio)

복잡도

시간: O(N log N)
공간: O(N)

문제