[백준] 5545번:최고의 피자 (python 파이썬)

문제

www.acmicpc.net/problem/5545

5545번: 최고의 피자

 

풀이 및 소스코드

그리디 알고리즘이다.

토핑의 열량을 입력 받은 후에 내림차순으로 정렬해준다.

먼저 토핑을 선택하지 않았을 경우, 즉 순수하게 도우만 선택한 경우의 1원당 열량의 값을 res 에 넣어두고 시작한다.

토핑의 열량을 높은 것 부터 차례로 넣어보면서 1원당 열량의 값이 감소할 때까지 반복한다.

감소한다면 그 전까지의 res 값을 출력하고 종료해준다.

 

import sys
input = sys.stdin.readline

n = int(input())
a, b = map(int, input().split())
c = int(input())
toping = [0]*n
for i in range(n):
    toping[i] = int(input())
toping.sort(reverse=True)
total = c
t_cnt = 0
res = total//a
while 1:
	for j in range(n):
		total += toping[j]
        t_cnt += 1
        now_res = total//(a+(b*t_cnt))
        if res<=now_res:
            res = now_res
        else:
            print(res)
            exit()