Rod Cutting Problem
길이가 n인 막대가 있고, 여기서 n = prices.length입니다. 길이가 k인 조각은 prices[k-1]에 판매됩니다. 막대를 원하는 만큼 정수 길이의 조각으로 자르거나, 한 조각으로 판매할 수 있습니다. 막대를 모두 판매하여 벌 수 있는 최대 금액을 반환하세요.
함수
- pricesinteger-array
- prices[k-1]는 길이가 k인 조각의 가격이며, 막대의 길이는 prices.length입니다
- 반환값integer
- 막대 전체가 벌 수 있는 최대 금액
제약 조건
1 ≤ prices.length ≤ 10001 ≤ prices[i] ≤ 105
예제
- 입력
- prices = [2, 5, 7, 8]
- 출력
- 10
- 설명
- 길이 2인 두 조각을 팔면 5 + 5 = 10을 얻습니다. 막대 전체를 팔면 8을 얻고, 길이 1인 조각 하나와 길이 3인 조각 하나를 팔면 2 + 7 = 9를 얻습니다.
- 입력
- prices = [1, 3, 8]
- 출력
- 8
- 설명
- 길이가 3인 막대 전체는 8에 판매됩니다. 가장 좋은 절단 방법인 길이 1과 2로 나누는 방법은 1 + 3 = 4만 벌 수 있으므로, 전혀 자르지 않습니다.
- 입력
- prices = [4, 6, 9, 11, 14]
- 출력
- 20
- 설명
- 길이 1인 조각은 더 긴 어떤 조각보다 단위 길이당 4를 더 받고 판매되며, 그런 조각 5개가 나오므로 막대를 길이 1인 조각 5개로 자르면 20을 벌 수 있습니다.
후속 질문
막대를 최대 m번 자를 수 있다면 어떨까요? 그렇다면 각 표 항목은 무엇을 알아야 할까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
막대를 자르는 모든 방법에는 왼쪽 끝에 1에서
n까지의 길이 중 하나인 첫 번째 조각이 있습니다. 그 조각을 팔고 나면, 결정해야 할 것은 무엇일까요?길이가
k인 첫 번째 조각을 자르고 나면, 나머지는 길이가n-k인 막대이며, 이를 판매하는 가장 좋은 방법은 이미 자른 조각과는 무관합니다. 따라서 더 짧은 모든 길이에 대한 최적의 가격이 필요하며, 그런 길이는n+1개뿐입니다.best[0..n]을 짧은 길이부터 긴 길이 순으로 채운다.best[0]은 0이고,best[len]은 1부터len까지의 모든k에 대해prices[k-1] + best[len-k]중 가장 큰 값이다.k = len을 선택하면 조각 전체를 판매하는 것이다.
풀이
길이가 n인 막대를 자르는 방법은 2^(n-1)가지입니다. 하지만 그 모든 방법을 구할 필요는 없습니다. 첫 번째 조각이 무엇이든, 나머지는 같은 질문을 하는 더 짧은 막대입니다. 따라서 길이마다 하나씩, 답은 n+1개만 있으면 되고, 가장 짧은 길이부터 계산하면 O(n²)단계가 걸립니다.
첫 번째 조각의 모든 길이를 시도해 보세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
계획이 무엇이든 왼쪽 끝에 있는 조각의 길이는 1부터 막대의 길이까지인 k이며 prices[k-1]의 값을 얻습니다. 나머지 계획은 길이가 length-k인 막대를 자릅니다. 따라서 길이가 0이면 best(length)는 0이고, 그렇지 않으면 모든 k에 대해 prices[k-1] + best(length-k) 중 가장 큰 값입니다. 여기서 k = length이면 막대 전체를 판매합니다. 모든 계획에는 첫 번째 조각이 있으므로, 이 최댓값은 모든 계획을 포함합니다.
각 호출은 더 짧은 모든 길이에 대해 분기하므로, 길이가 1단위 늘어날 때마다 호출 수가 두 배가 됩니다. 길이가 40인 막대는 약 2^40, 즉 10^12번의 호출을 발생시킵니다.
알고리즘
- 길이가 0일 때 0을 반환하는
best(length)를 작성하세요. - 첫 번째 조각
k를 1부터length까지 바꿔 가며prices[k-1] + best(length-k)를 계산하세요. - 그 값 중 가장 큰 값을 반환하세요.
best(n)을 반환하세요.
def cutRod(prices):
# The most money a rod of this length can earn
def best(length):
top = 0
for piece in range(1, length + 1):
# sell a first piece of this length, then cut the rest as well as possible
top = max(top, prices[piece - 1] + best(length - piece))
return top
return best(len(prices))길이별 최저 가격, 가장 짧은 길이부터
핵심 아이디어
재귀는 같은 값을 다시 계산합니다. best(2)는 best(3), best(4)와 그보다 긴 모든 막대에서 요청됩니다. 길이는 n+1개뿐이므로, 각 값을 배열 best에 한 번씩 계산해 저장합니다. 길이는 더 짧은 길이만 읽으므로, 배열을 0부터 채우면 값을 읽을 때마다 해당 값이 이미 준비되어 있습니다.
[2, 5, 7, 8]의 경우, best[1]은 2이고, best[2]는 2 + 2와 5 중 큰 값이므로 5이며, best[3]은 7입니다. best[4]는 2 + 7, 5 + 5, 7 + 2, 8 중 가장 큰 값이므로 10입니다.
0/1 배낭 문제와 달리, best[len-k]에는 이미 길이 k의 조각이 포함되어 있을 수 있으며, 길이는 원하는 만큼 자를 수 있으므로 이것이 바로 원하는 결과입니다. 길이 len은 첫 번째 조각으로 len가지 길이를 시도합니다. 전체 단계 수는 n(n+1)/2이며, 길이 1000인 막대의 경우 약 5 × 10^5입니다.
알고리즘
- 모두 0인 항목 n + 1개로
best를 만듭니다. - 1부터 n까지 각
length에 대해, 첫 번째 조각k를 1부터length까지 모두 시도합니다. prices[k-1] + best[length-k]를 계산하고, 가장 큰 값을best[length]에 저장합니다.best[n]을 반환합니다.
def cutRod(prices):
n = len(prices)
# best[length]: the most money a rod of that length can earn
best = [0] * (n + 1)
for length in range(1, n + 1):
for piece in range(1, length + 1):
# a first piece of this length, then the best for what is left
earned = prices[piece - 1] + best[length - piece]
if earned > best[length]:
best[length] = earned
return best[n]
함정과 경계 사례
- 길이
k에 대해prices[k]를 읽는 것. 그러면 모든 조각의 가격을 실제보다 한 단위 긴 크기로 계산하고k = n에서 범위를 벗어나므로prices[k-1]를 사용하세요. - 자르지 않은 조각인
k = length를 빠뜨리는 것. 그러면best[1]은 0으로 유지되고,[1, 3, 8]의 점수는 8이 아니라 3이 됩니다. - 단위당 가격이 가장 높은 방식으로 탐욕적으로 자르는 것.
[2, 7, 11, 13]에서는 길이 3이 단위당 가격이 가장 높지만, 그 조각의 가격 11에 남은 부분의 가격 2를 더하면 13인 반면 길이 2인 조각 두 개는 14의 가격을 얻습니다. - Python에서 하향식으로 메모이제이션하는 것. 재귀 호출은 막대의 길이만큼 깊게 중첩됩니다. 길이가 1000인 막대에서는 호출이 1001개 중첩되어 기본 한도인 1000을 초과합니다. 배열을 상향식으로 채우세요.
자주 묻는 질문4
막대 자르기 문제의 시간 복잡도는 얼마인가요?
이 표는 O(n²) 시간과 O(n) 메모리를 사용합니다. 길이 len에 대해 첫 번째 조각을 len개 시도하므로, 전체 시도 횟수는 n(n+1)/2입니다. 저장된 답이 없으면 각 길이에서 모든 더 짧은 길이를 호출하므로 길이가 n인 막대에 대해 재귀는 정확히 2^n번 호출됩니다.
로드 절단이 무제한 배낭 문제인 이유는 무엇인가요?
각 조각의 길이 k를 무게가 k이고 가치가 prices[k-1]인 아이템으로 취급하세요. 이 아이템은 개수 제한 없이 사용할 수 있으며, 막대는 용량이 n이고 정확히 채워야 하는 배낭으로 취급합니다. 그러면 아이템의 최대 총 가치는 막대의 최적 가격이 됩니다.
막대를 어디에서 자를지 어떻게 찾나요?
각 길이에 대해 가장 좋은 가격을 낸 첫 번째 조각 k를 저장합니다. 길이 n에서 시작하여 저장된 길이만큼 조각을 자르고, 남은 길이로 이동한 다음 0에 도달할 때까지 반복합니다. 이렇게 얻은 조각들이 하나의 최적 계획을 이룹니다.
모든 절단에 비용이 든다면 해결 방법은 어떻게 달라질까요?
막대 전체를 판매하면 자르지 않지만, 첫 번째 조각이 그 외의 길이면 모두 한 번 자릅니다. 따라서 best[len]은 prices[len-1]과 len보다 작은 k에 대해 가장 큰 prices[k-1] + best[len-k] - cost 중 더 큰 값이 됩니다. 나머지 표는 그대로입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def cutRod(prices):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
prices = [2, 5, 7, 8]
예상 출력
10