백준 5545번 Python / Greedy

문제 링크

https://www.acmicpc.net/problem/5545

5545번: 최고의 피자

 

풀이

n = int(input())
a,b = map(int, input().split())
c = int(input())
d = []
for _ in range(n):
    d.append(int(input()))
d.sort(reverse=True)

compare_kcal = c/a
total_price = a
total_kcal = c
cnt = 0
for i in range(len(d)):
    tmp = (total_kcal + d[i]) / (total_price + b)
    if tmp >=  compare_kcal:
        compare_kcal = tmp
        total_price += b
        total_kcal += d[i]
    else:
        break

print(int(total_kcal / total_price))

입력 값을 모두 받고, 토핑의 열량 내용이 들어있는 리스트를 내림차순으로 정렬했습니다.

for문으로 토핑의 개수만큼 반복를 하는데,

처음에는 1원당 도우의 열량을 기준으로 잡고 리스트에 해당하는 토핑의 열량과 토핑의 가격을 총 가격과 총 열량에 더해 비교할 1원당 열량(tmp)을 계산했습니다.

tmp(토핑을 넣었을 때 1원당 열량)와 compare_kcal(비교 전의 1원당 열량)를 비교해 tmp가 같거나 더 높다면 적용해주고 그렇지 않다면 그 이후의 리스트에 해당하는 열량들은 계산할 필요가 없기 때문에 break를 해주었습니다.

 

결과값으로 int(total_kcal / total_price)) 출력했습니다.