[알고리즘] 백준 5545 파이썬 - 최고의 피자

 

5545번: 최고의 피자

문제

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

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

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

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

 

문제풀이

import sys
input = sys.stdin.readline
n=int(input())
a,b=map(int,input().split())
c=int(input())
arr=[]
#01
for _ in range(n):
    arr.append(int(input()))
arr.sort(reverse=True)
tmp=[c,a]
ans=tmp[0]//tmp[1]
#02
for i in range(len(arr)):
    x=tmp[0]+arr[i]
    y=tmp[1]+b
    #03
    if ans<=x//y:
        ans=x//y
        tmp[0]=x
        tmp[1]=y
    else:
        break
print(ans)

- #01 : 입력값을 arr에 저장 후 내림차순으로 정렬한다.

           tmp의 초기값은 [도우의 열량, 도우의 가격]으로 설정한다.

           이후 ans에는 도우의 1원당 열량을 저장한다.

- #02 : x에는 도우의 열량 + 토핑의 열량을 저장한다.

           y에는 도우의 가격 + 토핑의 가격을 저장한다.

- #03 : 만약 ans보다 x//y가 크다면 즉 도우에 토핑을 더한 값이 1원당 열량이 높은 경우

           ans에 x//y를 저장 후 tmp의 값도 각각 x와y로 변경해준다.

          그렇지 않다면 더 효율적인 토핑은 모두 지나간 상태이니 for문을 종료해준다.

          (내림차순으로 정렬했기 때문에)

          마지막으로 구한 ans를 출력해준다.