5) Tabulation 방식의 새꼼달꼼 장사 최대 수익 함수

5. Tabulation 방식의 새꼼달꼼 장사 최대 수익 함수

 

1) 일반 풀이

def max_profit(price_list, count):
    if count <2:
        return price_list[count]

    profit = 0

    if count < len(price_list):
        profit = price_list[count]

    for i in range(1,len(price_list)-1):
        if count < i:
            break
        if profit < price_list[i] + max_profit(price_list,count - i):
            profit = price_list[i] + max_profit(price_list,count - i)
            
    return profit

# 테스트
print(max_profit([0, 200, 600, 900, 1200, 2000], 5))
print(max_profit([0, 300, 600, 700, 1100, 1400], 8))
print(max_profit([0, 100, 200, 400, 600, 900, 1200, 1300, 1500, 1800], 9))

# 결과  
2000 
2400 
1800

2) Tabulation 방식

def max_profit(price_list, count):
    profit_table = [0]

    for i in range(1, count + 1):

        profit = 0

        if i < len(price_list):
            profit = price_list[i]

        for j in range(1, i // 2 + 1):
            profit = max(profit, profit_table[j] + profit_table[i - j])

        profit_table.append(profit)

    return profit_table[count]

# 테스트
print(max_profit([0, 200, 600, 900, 1200, 2000], 5))
print(max_profit([0, 300, 600, 700, 1100, 1400], 8))
print(max_profit([0, 100, 200, 400, 600, 900, 1200, 1300, 1500, 1800], 9))

# 결과 : 
2000 
2400
1800

 

풀이 (1)

풀이 (2)