Python – 막대를 잘라 동일한 길이의 막대만 판매할 때 최대 이익 구하기

문제 설명

막대 길이 목록 rodLen과 두 개의 정수 profit(단위 길이당 이익), cost(절단 1회당 비용)가 주어졌다고 가정해 보겠습니다. 막대의 단위 길이마다 이익을 얻을 수 있지만, 판매할 수 있는 막대는 모두 길이가 서로 같아야 합니다. 또한 막대를 정수 길이를 가진 두 조각으로 자를 수 있으며, 절단할 때마다 cost만큼의 비용을 지불해야 합니다. 막대는 원하는 만큼 몇 번이든 잘라도 됩니다. 이때 얻을 수 있는 최대 이익을 구하는 것이 목표입니다.

예를 들어 입력이 rodLen = [7, 10], profit = 6, cost = 4라면 출력은 82가 됩니다. 길이 7인 막대를 길이 5와 2인 두 막대로 자르고, 길이 10인 막대는 길이 5인 두 막대로 자릅니다. 그러면 길이 5인 막대 3개를 모두 판매하여 총 이익 (5 + 5 + 5) × 6 − (2 × 4) = 82를 얻을 수 있습니다.

해결 방법

이 문제는 다음 단계에 따라 해결할 수 있습니다.

n := rodLen의 크기
n이 0이면 0을 반환
l_max := rodLen의 최댓값
p_max := 0
cuts를 1부터 l_max까지 반복:
- p_cut := 0
- rodLen의 각 rod_len에 대해 반복:
  - rod_len < cuts이면 다음 반복으로 진행
  - c_count := rod_len // cuts (정수 나눗셈)
  - total_len := c_count × cuts
  - rod_len == total_len이면 c_count := c_count − 1
  - curr_profit := total_len × profit − cost × c_count
  - curr_profit < 0이면 다음 반복으로 진행
  - p_cut := p_cut + curr_profit
- p_max := max(p_max, p_cut)
p_max 반환

알고리즘의 핵심 아이디어

판매 가능한 막대의 길이는 1부터 가장 긴 막대의 길이 사이에 있는 정수 중 하나입니다. 따라서 가능한 모든 절단 길이(cuts)를 하나씩 시도하면서, 각 막대를 해당 길이로 잘랐을 때 얻을 수 있는 순이익(판매 수익 − 절단 비용)을 계산합니다. 특정 막대에서 순이익이 음수가 되면 그 막대는 아예 판매하지 않는 것이 유리하므로 건너뛰고, 모든 경우를 확인한 뒤 가장 큰 값을 정답으로 반환합니다.

예제 코드

아래 구현을 통해 더 잘 이해해 보겠습니다.

def solve(rodLen, profit, cost):
    n = len(rodLen)
    if n == 0:
        return 0
    l_max = max(rodLen)
    p_max = 0

    for cuts in range(1, l_max + 1):
        p_cut = 0
        for rod_len in rodLen:
            if rod_len < cuts:
                continue
            c_count = rod_len // cuts
            total_len = c_count * cuts
            if rod_len == total_len:
                c_count -= 1
            curr_profit = total_len * profit - cost * c_count
            if curr_profit < 0:
                continue
            p_cut += curr_profit
        p_max = max(p_max, p_cut)
    return p_max

rodLen = [7, 10]
profit = 6
cost = 4
print(solve(rodLen, profit, cost))

입력

[7, 10], 6, 4