5.8 철근 자르기 - 메모전략

특정 길이에 대해 캐시에 값이 존재한다면
그 값을 바로 반환하면 실행 속도가 개선될 수 있음.
(이 전략을 메모전략이라고 부름)

위의 내용을 기반으로 소스를 작성하면 다음과 같다.

import sys

sys.setrecursionlimit(10 ** 5)
cache = [0 for _ in range(100000)]


def solve_memo(v, n):
    if n <= 0:
        return 0
    global cache

    if cache[n - 1] != 0:
        return cache[n - 1]

    cache[n - 1] = -987654321

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

    return cache[n - 1]


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

재귀를 사용할 때와 거의 유사한 형태였다.
생각보다 바뀌는 소스가 별로 없어서 놀람.