[알고리즘 일기] 23. 최대 곱 구하기

 

 

문제 23. (2021-05-23)

 

최대 곱 구하기

여럿이서 카드 게임을 하고 있는데, 각 플레이어는 3장의 카드를 들고 있습니다. 위의 경우 첫 번째 플레이어는 1, 2, 3을 들고 있고, 두 번째 플레이어는 4, 6, 1을 들고 있고, 세 번째 플레이어는 8, 2, 4를 들고 있습니다.

 

 

주의사항

* 함수 max_product는 한 사람당 카드를 하나씩 뽑아서 모두 곱했을 때 가능한 최대 곱을 리턴합니다.

 

 

❧ 테스트 셋

def max_product(card_lists):
    #Code

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

 

❧ 출력 예시

24
244944
10800
12600

 

 

---

❧ 정답

def max_product(card_lists):
    result = 1
    for i in card_lists:
        result *= max(i)
    return result

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

 

1️⃣ 탐욕 알고리즘 사용

2️⃣ 반복문을 돌면서 카드 뭉치를 하나씩 본다 → result에 각 뭉치의 최댓값을 곱해 준다

3️⃣ 최적 부분 구조 : (n-1) 번째까지의 최대 곱 X n번째 최대값

4️⃣ 탐욕적 선택 속성 : 각 단계의 카드 조합 중 최대값 선택

 

728x90