algorithm. Introduction to Algorithms 3rd 15.1 Rod cutting

Rod cutting(Dynamic programming)



문제: 위의 가격이 정해져 있을 때 n length인 막대기를 짤라 파는 경우 중 가장 수익이 높은 값은?

생각은 간단하다.

MaxPrice[n] = Max(p[i] + MaxPrice[n - i])

이 것을 코드화 하면

import sys 
P = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30] 

def rodCut(p, n): 
        if n == 0: return 0
        ret = 0 
        for i in range(1, n + 1): 
                ret = max(ret, P[i] + rodCut(p, n - i)) 
        return ret 

rl = lambda: sys.stdin.readline()
print(rodCut(P, int(rl())))

이고
dynamic programming을 적용해서 r에 저장하면

def memorizedCutRodAux(p, n, r): 
        if n == 0:
                r[n] = 0 
                return r[n]
        if r[n] >= 0:
                return r[n]
        ret = 0 
        for i in range(1, n + 1): 
                r[n] = ret = max(ret, P[i] + memorizedCutRodAux(p, n - i, r)) 
        return r[n]

def memorizedCutRod(p, n): 
        r = [-1] * (n + 1)
        return memorizedCutRodAux(p, n, r)
print(memorizedCutRod(P, int(rl())))

그리고 이 것을 bottom up 방식으로 구현하면

def bottomUpMemorizedCutRod(p, n): 
        r = [-1] * (n + 1)
        r[0] = 0 
        for i in range(1, n + 1): 
                ret = 0 
                for j in range(i + 1): 
                        r[n] = ret = max(ret, p[i] + r[n - i]) 
        return r[n]
print(bottomUpMemorizedCutRod(P, int(rl())))

이다.
시간 제약에 걸릴 때 가장 먼저 생각해보는 방법이다..

덧. TopCoder 알고리즘 책에는 변수가 여러가지 인 경우 배열로 저장하기 위한 방법을 표현한 문제가 있다.