[Dynamic Programming] 새꼼달꼼 장사 Tabulation

실습 설명

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

• price_list: 개수별 가격이 정리되어 있는 리스트
• count: 판매할 새꼼달꼼 개수

예를 들어 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(price_list, count):
    # 개수별로 가능한 최대 수익을 저장하는 리스트
    # 새꼼달꼼 0개면 0원
    profit_table = [0]

    # 개수 1부터 count까지 계산하기 위해 반복문
    for i in range(1, count + 1):
        # profit은 count개를 팔아서 가능한 최대 수익을 저장하는 변수
        # 팔려고 하는 총개수에 대한 가격이 price_list에 있으면 일단 그 가격으로 설정
        # 팔려고 하는 총개수에 대한 가격이 price_list에 없으면 일단 0으로 설정   
        if i < len(price_list):
            profit = price_list[i]
        else:
            profit = 0

        # count개를 팔 수 있는 조합들을 비교해서, 가능한 최대 수익을 찾는다
        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))

해결과정
 
계산된 최대 수익을 저장시켜 놓을 표(table)가 있어야 하기 때문에 profit_table 리스트를 만들어준다.
새꼼달꼼 0개로 가능한 최대 수익은 0원이다. 그러면 profit_table은 처음에 이렇게 정의할 수 있는데,

profit_table = [0]

이제 profit_table을 인덱스 1부터 인덱스 count까지 채워 나간 후에, 인덱스 count의 항목을 리턴하면 될 것 같다.
 
Memoization으로 풀 때에도 생각했던 부분을 다시 기억해보면,
 
새꼼달꼼 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개를 팔아서 가능한 최대 수익

위 네 경우를 비교하면 된다.
반복문의 기준은 memoization 때와 같다.