[알고리즘] 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 + 400을 해서 총 1200원의 수익을 낼 수 있겠죠.

 

실습

def max_profit(price_list, 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))

힌트1

계산된 최대 수익을 저장시켜 놓을 표가 필요합니다. 우리는 리스트를 표처럼 사용할 수 있습니다. 그 리스트를 profit_table라고 하겠습니다.

 

새꼼달꼼 0개로 가능한 최대 수익은 0원 입니다. 그러면 profit_table은 처음에 이렇게 정의 할 수 있습니다.

profit_table = [0]

이제 profit_table을 인덱스 1부터 인덱스 count까지 채워 나간 후에 인덱스 count의항목을 리턴하면 되겠죠?

 

힌트2

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개를 팔아서 가능한 최대 수익

 

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

 

힌트 3

def max_profit(price_list, count):
    # 개수별로 가능한 최대 수익을 저장하는 리스트
    # 새꼼달꼼 0개면 0원
    profit_table = [0]

    # 개수 1부터 count까지 계산하기 위해 반복문
    for i in range(1, count + 1):
        # count개를 팔 수 있는 조합들을 비교해서, 가능한 최대 수익을 찾는다
        # 가능한 최대 수익을 profit_table에 넣는다

    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))

 

 

 

답안

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))