[Greedy Algorithm] 최대 곱 구하기

def max_product(card_lists):
    # 여기에 코드를 작성하세요
    max_card = []
    
    for i in card_lists:
        max_card.append(max(i))
        
    max_num = max_card[0]
    
    for j in range(1, len(max_card)):
        max_num *= max_card[j]
        
    
    return max_num


#########모범 답안#########

def max_product(card_lists):
    # 누적된 곱을 저장하는 변수
    product = 1

    # 반복문을 돌면서 카드 뭉치를 하나씩 본다
    for card_list in card_lists:
        # product에 각 뭉치의 최댓값을 곱해 준다
        product *= max(card_list)

    return product


# 테스트 코드
test_cards1 = [[1, 6, 5], [4, 2, 3]]
print(max_product(test_cards1))

test_cards2 = [[9, 7, 8], [9, 2, 3], [9, 8, 1], [2, 8, 3], [1, 3, 6], [7, 7, 4]]
print(max_product(test_cards2))

test_cards3 = [[1, 2, 3], [4, 6, 1], [8, 2, 4], [3, 2, 5], [5, 2, 3], [3, 2, 1]]
print(max_product(test_cards3))

test_cards4 = [[5, 5, 5], [4, 3, 5], [1, 1, 1], [9, 8, 3], [2, 8, 4], [5, 7, 4]]
print(max_product(test_cards4))

해결과정
 
이 문제에서 할 수 있는 탐욕적 선택은 각 뭉치에서 가장 큰 값을 선택하는 것...!
최적부분구조와, 탐욕적 선택 속성이 있으면, greedy algorithm적 접근 방식으로 푸는 연습을 해보자