4) 장사 분석, 최대 수익 출력 함수

4. 장사 분석, 최대 수익 출력 함수

# Base Case: 0개 혹은 1개면 부분 문제로 나눌 필요가 없기 때문에 가격을 바로 리턴한다

# 이미 계산한 값이면 cache에 저장된 값을 리턴한다

# profit은 count개를 팔아서 가능한 최대 수익을 저장하는 변수
# 팔려고 하는 총개수에 대한 가격이 price_list에 없으면 일단 0으로 설정
# 팔려고 하는 총개수에 대한 가격이 price_list에 있으면 일단 그 가격으로 설정

# count개를 팔 수 있는 조합들을 비교해서, 가능한 최대 수익을 profit에 저장

# 계산된 최대 수익을 cache에 저장

 

 풀이 (1)

def max_profit_memo(price_list, count, cache):
    # Base Case: 0개 혹은 1개면 부분 문제로 나눌 필요가 없기 때문에 가격을 바로 리턴한다
    if count < 2:
        cache[count] = price_list[count]
        return price_list[count]

    # 이미 계산한 값이면 cache에 저장된 값을 리턴한다
    if count in cache:
        return cache[count]

    # profit은 count개를 팔아서 가능한 최대 수익을 저장하는 변수
    # 팔려고 하는 총개수에 대한 가격이 price_list에 없으면 일단 0으로 설정
    # 팔려고 하는 총개수에 대한 가격이 price_list에 있으면 일단 그 가격으로 설정
    if count < len(price_list):
        profit = price_list[count]
    else:
        profit = 0

    # count개를 팔 수 있는 조합들을 비교해서, 가능한 최대 수익을 profit에 저장
    for i in range(1, count // 2 + 1):
        profit = max(profit, max_profit_memo(price_list, i, cache) 
                 + max_profit_memo(price_list, count - i, cache))

    # 계산된 최대 수익을 cache에 저장
    cache[count] = profit

    return profit

def max_profit(price_list, count):
    max_profit_cache = {}

    return max_profit_memo(price_list, count, max_profit_cache)

 

 

 풀이 (2)

def max_profit_memo(price_list, count, cache):
    if count < 2:
        cache[count] = price_list[count]
        return price_list[count]

    if count in cache:
        return cache[count]

    maximum = 0

    for i in range(1, len(price_list)):
        if count < i:
            break
        if maximum < price_list[i] + max_profit_memo(price_list, count - i, cache):
            maximum = price_list[i] + max_profit_memo(price_list, count - i, cache)

    cache[count] = maximum
    return cache[count]


def max_profit(price_list, count):
    max_profit_cache = {}

    return max_profit_memo(price_list, count, max_profit_cache)

 

# 테스트
print(max_profit([0, 100, 400, 800, 900, 1000], 5))
print(max_profit([0, 100, 400, 800, 900, 1000], 10))
print(max_profit([0, 100, 400, 800, 900, 1000, 1400, 1600, 2100, 2200], 9))

결과
1200
2500
2400

 

 

 

풀이 (1)

풀이 (2)