[Dynamic Programming] 새꼼달꼼 장사 Memoization

실습 설명

솔희는 학원 쉬는 시간에 친구들을 상대로 새꼼달꼼 장사를 합니다. 그러다 문뜩, 갖고 있는 새꼼달꼼으로 벌어들일 수 있는 최대 수익이 궁금해졌습니다.
가능한 최대 수익을 리턴시켜 주는 함수 max_profit_memo를 Memoization 방식으로 작성해 보세요. max_profit_memo는 파라미터 세 개를 받습니다.

• price_list: 개수별 가격이 정리되어 있는 리스트
• count: 판매할 새꼼달꼼 개수
• cache: 개수별 최대 수익이 저장되어 있는 사전

예를 들어 price_list가 [0, 100, 400, 800, 900, 1000]이라면, 아래처럼 가격이 책정된 거예요.

1. 새꼼달꼼 0개에 0원
2. 새꼼달꼼 1개에 100원
3. 새꼼달꼼 2개에 400원
4. 새꼼달꼼 3개에 800원
5. 새꼼달꼼 4개에 900원
6. 새꼼달꼼 5개에 1000원

만약 솔희가 새꼼달꼼 5개를 판매한다면 최대로 얼마를 벌 수 있을까요?
한 친구에게 3개 팔고 다른 친구에게 2개를 팔면, 800+400800+400을 해서 총 1200원의 수익을 낼 수 있겠죠.

실습 결과

# 테스트 코드
print(max_profit([0, 100, 400, 800, 900, 1000], 5))

1200

 

def max_profit_memo(price_list, count, cache):
    # 여기에 코드를 작성하세요
    # base case: 0개 혹은 1개면 부분 문제로 나눌 필요가 없기 때문에 가격 바로 return
    if count <= 1:
        cache[count] = price_list[count]
        return cache[count]
    
    # 이미 계산한 값이면 cache에 저장된 값 리턴
    if count in cache:
        return cache[count]
    
    # 아직 최대 수익을 계산하지 않았으면:
    # 계산한 후 cache에 저장
    # 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)


# 테스트 코드
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))

해결과정
우선 Memoization 방식으로 문제를 푼다? -> 재귀함수를 사용한다. -> base case와 recursive case로 나눈다.
 
base case : 새꼼달꼼 0개 혹은 1개를 파려고하면, 부분 문제로 나눌 필요 없이 바로 주어진 가격을 리턴한다.
 
recursive case : 
max_profit_memo(price_list, i, cache)를 호출했다고 가정했을 때

• 새꼼달꼼 i개를 팔아서 가능한 최대 수익을 이미 계산한 경우, 즉 cache[i]가 존재하는 경우
• 새꼼달꼼 i개를 팔아서 가능한 최대 수익을 아직 계산하지 않은 경우, 즉 cache[i]가 존재하지 않는 경우

두가지로 나누어서 생각할 수 있을 것 같다.
 
새꼼달꼼 2개를 팔아서 가능한 최대 수익은 어떻게 찾아낼 수 있을까?

1. 2개를 한 명에게 팔 때의 가격
2. 1개를 팔아서 가능한 최대 수익 + 1개를 팔아서 가능한 최대 수익

위 두 경우를 비교하면 된다. 그렇다면 새꼼달꼼 3개를 팔아서 가능한 최대 수익은 어떻게 찾아낼 수 있을까?

1. 3개를 한 명에게 팔 때의 가격
2. 2개를 팔아서 가능한 최대 수익 + 1개를 팔아서 가능한 최대 수익

위 두 경우를 비교하면 된다. 그렇다면 새꼼달꼼 4개를 팔아서 가능한 최대 수익은 어떻게 찾아낼 수 있을까?

1. 4개를 한 명에게 팔 때의 가격
2. 3개를 팔아서 가능한 최대 수익 + 1개를 팔아서 가능한 최대 수익
3. 2개를 팔아서 가능한 최대 수익 + 2개를 팔아서 가능한 최대 수익

위 세 경우를 비교하면 된다. 그렇다면 새꼼달꼼 5개를 팔아서 가능한 최대 수익은 어떻게 찾아낼 수 있을까?

1. 5개를 한 명에게 팔 때의 가격
2. 4개를 팔아서 가능한 최대 수익 + 1개를 팔아서 가능한 최대 수익
3. 3개를 팔아서 가능한 최대 수익 + 2개를 팔아서 가능한 최대 수익

위 세 경우를 비교하면 된다. 그렇다면 새꼼달꼼 6개를 팔아서 가능한 최대 수익은 어떻게 찾아낼 수 있을까?

1. 6개를 한 명에게 팔 때의 가격
2. 5개를 팔아서 가능한 최대 수익 + 1개를 팔아서 가능한 최대 수익
3. 4개를 팔아서 가능한 최대 수익 + 2개를 팔아서 가능한 최대 수익
4. 3개를 팔아서 가능한 최대 수익 + 3개를 팔아서 가능한 최대 수익

위 네 경우를 비교하면 된다. 패턴 파악 후 코드 작성