5.8 철근 자르기 - DP

지난 시간의 소스와 거의 동일한 형태다.
다만, 더 이상 재귀 호출은 사용하지 않고 반복문으로 끝냄.
2중 for문 사용으로 시간 복잡도는 최대 O(n^2)가 됨.

def solve_dp(v, n):
    cache = [0 for _ in range(n+1)]

    for i in range(1, n + 1):
        cache[i] = -987654321

        for j in range(1, i + 1):
            cache[i] = max(cache[i], v[j] + cache[i - j]) # 핵심 line

    return cache[n]


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

v가 2, 3, 6, 7 일 때를 기준으로 소스를 분석해보면 다음과 같다.

cache [1]의 초기값은 -987654321
그다음 반복문을 거치면
cache [1] = max(-987654321, 2 + 0) = 2 가 된다.

cache [2]의 초기값도 -987654321
그다음 반복문을 거치면
cache [2] = max(-987654321, 2 + 2) = 4
cache [2] = max(4, 3 + 0) = 4
결국 1짜리 막대기 두 개의 값 와 2짜리 막대기 한 개의 값을 비교해서 구하는 것과 동일하다.

cache [3]의 초기값도 -987654321
그다음 반복문을 거치면
cache [3] = max(-987654321, 2 + 4) = 6
cache [3] = max(6, 2 + 3) = 6
cache [3] = max(6, 6 + 0) = 6
이것도 결국은 2짜리 막대기를 구하는데 최댓값 + 1짜리 막대기 혹은 3짜리 막대기 1개 중 최댓값을 구하는 것과 동일하다. 

마지막으로 cache [4]의 초기값 역시 -987654321
그다음 반복문을 거치면
cache [4] = max(-987654321, 2 + 6) = 8
cache [4] = max(8, 3 + 4) = 8
cache [4] = max(8, 6 + 2) = 8
cache [4] = max(8, 8 + 0) = 8
마지막도 기존까지 구했던 막대기들의 최댓값에 부족한 길이들을 더해서 최댓값을 구하는 로직이라고 볼 수 있다.

오랜만에 잘 이해가 안 가는 부분을 디버깅해가면서 추적해보니 이해가 꽤 잘된다.
재귀의 경우 stack을 하나씩 봐야 하는 불편함이 있는데, 역시 DP는 로직 확인 하기가 훨씬 수월하다.