[baekjoon] 백준 1421번(파이썬): 나무꾼 이다솜

문제

1421번: 나무꾼 이다솜

알고리즘

- 반복문을 통해 나무를 1부터 제일 긴 나무의 길이만큼 잘라본다.

- 반복문을 통해 모든 나무를 확인한다.

- 나무를 자른 후 개수와 남은 나무의 길이를 구한다.

- 남은 나무의 길이가 있다면 자른 나무 수만큼 비용을 낸다.

- 남은 나무의 길이가 없다면 자른 나무 수 -1 만큼 비용을 낸다.

- 자른 나무를 판 후 이익이 나는지 확인한다.

- 이익이 난다면 money에 이익을 더한다.

- 모든 나무를 확인한 후에 money가 이익의 총합 중에 가장 큰 값인지 확인한다.

코드

import sys

n, c, w = map(int, sys.stdin.readline().split())
trees = [int(sys.stdin.readline()) for _ in range(n)]
max_money = 0

# 반복문을 통해 나무를 1부터 제일 긴 나무의 길이만큼 잘라본다.
for i in range(1, max(trees) + 1):
    money = 0

    # 반복문을 통해 나무를 확인
    for j in trees:
        # cnt : 자른 나무 수
        # remain : 남은 나무의 길이
        cnt, remain = divmod(j, i)

        # 나무가 남았다면 자른 나무 수만큼 비용을 낸다.
        if remain:
            expense = cnt * c

        # 나무가 남지 않았다면 자른 나무 수 - 1만큼 비용을 낸다.
        else:
            expense = (cnt - 1) * c

        # 자른 나무를 판다.
        target = (cnt * w * i) - expense

        # 자른 나무를 팔 때 이익이 안난다면 continue
        if target < 0:
            continue

        # money에 이익을 더한다.
        money += target

    # 이익의 총합이 가장 큰 결과를 찾는다.
    if money >= max_money:
        max_money = money

print(max_money)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법