[백준 5545] 최고의 피자

꾸준히 블로그를 쓰기 위해 간단한 백준 문제를 풀고 풀이를 간단히 올리려 한다.

 

5545번: 최고의 피자

N가지의 토핑을 적절히 선택하여 단위 금액당(1원 당) 열량이 가장 높은 값을 찾는 문제이다. 문제 상에서 "최고의 피자"는 단위 금액당 열량이 가장 높은 값을 의미한다.

 

모든 토핑의 가격은 B원으로 토핑의 열량이 가장 큰 것부터 보면서 "최고의 피자"를 찾으면 된다.

토핑을 추가할 때 값이 떨어진다면 해당 토핑 전까지만 선택하면 된다. 이를 판단하는 방법은 아래와 같다.

 

현재까지 선택한 토핑의 열량 + 도우의 열량을 y, 현재까지 선택한 토핑의 가격 + 도우의 가격을 x, i번째 토핑의 열량을 b, i번째 토핑의 가격을 a라고 가정해보자.

 

$\Large \frac {y+b} {x+a} \ge \frac {y} {x}$

 

토핑의 열량이 큰 것부터 보면서 위 식을 만족하지 않을 때까지 토핑을 선택하면 된다.

 

import sys

def input():
    return sys.stdin.readline().rstrip()

N = int(input())
A, B = map(int, input().split())
C = int(input())
arr = sorted([int(input()) for _ in range(N)], key=lambda x:-x)

for x in arr:
    if A * x < B * C:
        break
    A += B
    C += x

print(int(C/A))