5.8 철근 자르기 - 재귀

철근이 길이에 따라 서로 다른 가격으로 판매될 때
특정 길이의 철근을 어떻게 잘라야 이익을 최대화할 수 있을지 구하는 문제다.

이 문제의 풀이도 동전 문제와 별반 다를 게 없다.
종료 조건은 남은 철근이 없을 때이며
반복문을 돌며 최대 이익을 구하도록 재귀 호출하면 된다.
위의 내용을 코드로 옮기면 다음과 같다.

import sys

sys.setrecursionlimit(10 ** 5)


def solve(v, n):
    if n <= 0:
        return 0

    price = -987654321

    for i in range(1, n + 1):
        price = max(price, v[i] + solve(v, n - i))

    return price


if __name__ == '__main__':
    v = [0] + list(map(int, input().split()))
    print(solve(v, len(v) - 1))

처음 소스 작성할 때
v와 n을 모두 입력받았는데 문제를 다시 보니 굳이 그럴 필요가 없어서 v 기준으로 n을 구해줌.
만약 v에 [0]을 추가해주지 않으려면 solve 쪽의 price 구하는 로직의 수정이 필요함. (+1로 해주면 됨)

소스와 개념은 정말 동전 문제와 유사한 패턴으로 보인다.
결국은 하위 문제의 반복이라고 할 수 있는데
예를 들어 n이 10인 경우(v의 엘리먼트가 10개)
n이 9인 경우의 최댓값 + v [1]과
n이 8인 경우의 최댓값 + v [2]과
n이 7인 경우의 최댓값 + v [3]과
n이 6인 경우의 최댓값 + v [4]과
n이 5인 경우의 최댓값 + v [5]과
n이 4인 경우의 최댓값 + v [6]과
n이 3인 경우의 최댓값 + v [7]과
n이 2인 경우의 최댓값 + v [8]과
n이 1인 경우의 최댓값 + v [9]과
n이 0인 경우의 최댓값(결국 0) + v [10] 중에 최댓값을 구하면 되는 문제가 된다.

여기서 핵심은 'n이 9인 경우의 최댓값'을 구하려면 다시
n이 8인 경우의 최댓값 + v [1]과
n이 7인 경우의 최댓값 + v [2]과
n이 6인 경우의 최댓값 + v [3]과
n이 5인 경우의 최댓값 + v [4]과
n이 4인 경우의 최댓값 + v [5]과
n이 3인 경우의 최댓값 + v [6]과
n이 2인 경우의 최댓값 + v [7]과
n이 1인 경우의 최댓값 + v [8]과
n이 0인 경우의 최댓값(결국 0) + v [9] 중에 최댓값을 구하면 되는 문제가 된다.

결국은 하위 문제의 반복이라고 볼 수 있다.

책에 위의 내용일 필요 할거 같은데.. 그냥 점화식만 딱 적어 놓고 끝 -_-;;
아마도 책 전반에서 설명한 내용이라 생략한 거 같긴 한데..
독자에게는 크게 도움이 안 될 것으로 보이기도 한다.
하긴 뭐 어차피 DP로 바꿔서 풀긴 할 테니;; 크게 상관없는 걸까?