[백준] 1421 나무꾼 이다솜 - python

문제 링크
https://www.acmicpc.net/problem/1421

시도1. 실패

from math import ceil 

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

for i in range(1,max(trees)+1):
  L = sum([(tree // i) for tree in trees])
  cost = sum([(ceil(tree/i)-1)*c for tree in trees])
  profit.append(L * i * w - cost)
  
print(max(profit))

• 접근방법 : 완전 탐색
• 시간복잡도 : O(n²)
• 각 나무별로 잘라서 파는 금액보다 자르는데 드는 비용이 더 큰 경우를 고려하지 않았다 (나무를 안파는게 나은 경우가 존재함)

시도2. 성공

from math import ceil 

n, c, w = map(int, input().split())
trees = [int(input()) for _ in range(n)]
profits=[]
               
for L in range(1,max(trees)+1):
  profit = []
  for tree in trees:
      profit.append(max(0,(tree // L)*L*w - (ceil(tree / L)-1)*c))
  profits.append(sum(profit))

print(max(profits))

• 접근방법 : 완전 탐색
• 시간복잡도 : O(n²)