[백준] 1421 나무꾼 이다솜 (Python/파이썬)

<문제 링크>

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

1421번: 나무꾼 이다솜

 

<풀이 전략>

1. 기본적으로 나무가 50개 이하고 나무 길이가 10000이하라서 O(N^2)여도 대략 50 * 10000 = 50만 번 연산을 해서 완전 탐색으로 풀 수 있습니다.

2. 길이가 1부터 가장 긴 나무까지 모두 잘라보며 최대 이익을 구하면 되는데 2가지 함정이 있습니다. 

3. 첫째, 나무가 남는 부분 없이 딱 잘릴 경우에는 잘린 횟수를 1 빼줘야됩니다 (ex 길이가 8인 나무를 2의 길이로 자를 경우에 3번만에 자를 수 있지만 8 // 2 = 4입니다)

4. 둘째, 자르는 비용이 이익보다 큰 경우에는 아예 안 자르고 건너 뛰어야 됩니다.

5. 위 두 가지만 주의해서 풀면 됩니다.

 

<정답 코드>

import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

# 230508 1451 나무꾼 이다솜

# 정답코드

N, C, W = map(int, input().split())

trees = []

for _ in range(N):
    trees.append(int(input()))

max_tree = max(trees)

answer = 0

# 1 ~ 가장 긴 나무의 길이까지 자르기
for i in range(1, max_tree + 1):

    temp = 0

    for tree in trees:

        sale = (tree // i) * W * i
        # 딱 맞게 잘릴 경우에는 1 빼기
        cost = C * (tree // i if tree % i else tree // i - 1)
        profit = sale - cost

        # 이익이 0보다 클 경우에만 더해주기
        if profit > 0:
            temp += profit

    answer = max(answer, temp)

print(answer)