BOJ 1421 - 나무꾼 이다솜

문제

BOJ 1421 - 나무꾼 이다솜

N개의 나무가 있다. 같은 길이 L로 잘라서 팔 때, 1cm당 W원의 수익을 얻고 한 번 자를 때 C원의 비용이 든다. 최대 수익을 구하라.

입력

첫째 줄에 나무 수 N, 자르는 비용 C, 1cm당 가격 W, 이후 N줄에 각 나무의 길이가 주어진다.

출력

최대 수익을 출력한다.

예제

풀이

가능한 모든 길이 L에 대해 모든 나무의 수익을 계산하고, 최대값을 구한다.

1. L을 1부터 최대 나무 길이까지 순회한다
2. 각 나무에 대해: 토막 수 = tree // L, 자르는 횟수 = ceil(tree / L) - 1
3. 수익 = 토막 수 × L × W - 자르는 횟수 × C (음수이면 0)
4. 모든 나무의 수익 합이 최대인 L을 선택한다

핵심 아이디어: 최대 나무 길이가 10000이하이므로 모든 L에 대해 브루트포스로 O(M × N)에 해결 가능하다.

코드

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(M * N) (M은 최대 나무 길이, N은 나무 개수)
• 공간: O(N)