1421 나무꾼 이다솜

문제

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

1421번: 나무꾼 이다솜

 

접근

• 나무의 개수가 50보다 작고 자를 수 있는 나무 길이가 10000보다 작으므로, 자를 수 있는 모든 길이에 대해 벌 수 있는 돈을 계산해서 최댓값을 구했다.
• 주의할 점은 가지고 있는 나무를 전부 잘라서 팔아야하는 것은 아니므로, 해당 나무를 팔았을 때 얻는 비용과 자를 때 드는 비용의 차가 양수일때만 나무를 판다.

 

풀이

n, c, w = map(int, input().split())
a = [int(input()) for _ in range(n)]

ans = 0
for i in range(1, 10001):
    tmp = 0
    for x in a:
        cost = 0
        m, d = divmod(x, i)
        if d == 0:
            cost += (m - 1) * c
        else:
            cost += m * c

        if m * w * i - cost > 0:
            tmp += m * w * i - cost 
            
    ans = max(ans, tmp)
    
print(ans)