[백준] 최고의 피자

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

5545번: 최고의 피자

 

초기의 값 C // A 를 기준으로 분모와 분자에 값을 계속 더하여 최고의 피자를 찾는 문제이다.

 

분모는 토핑이 추가될 때마다 일정하게 더해주고(B) 분자에는 토핑의 열량을 더해준다. 즉, 토핑의 열량을 큰 것부터 처리했을 때, answer 이 감소하는 시점부터 토핑의 열량은 계속 전보다 작은 값을 더해주므로 증가하고 감소하는 시점에 break 를 걸어준다. 수학적으로 증명하기는 쉽다.

 

예를 들면 1과 1.5는 소수점을 버리므로 같은 것으로 판단한다. 그러면 증가하는 것이 판별되지 않으므로 'answer <= temp' 로 표현해준다. 

 

import sys

N = int(sys.stdin.readline())
A, B = map(int, sys.stdin.readline().split())
C = int(sys.stdin.readline())
D = []
k = 0
temp = 0
answer = 0

for i in range(N):
    D.append(int(sys.stdin.readline()))

D.sort()

while D:
    temp = C // (A + (B * k))
    
    if answer <= temp:
        answer = temp
        k += 1
        C += D.pop()
    else:
        break

print(answer)