링크 : https://leetcode.com/problems/maximum-number-of-coins-you-can-get/

description

There are 3n piles of coins of varying size, you and your friends will take piles of coins as follows:

In each step, you will choose any 3 piles of coins (not necessarily consecutive). Of your choice, Alice will pick the pile with the maximum number of coins. You will pick the next pile with maximum number of coins. Your friend Bob will pick the last pile. Repeat until there are no more piles of coins. Given an array of integers piles where piles[i] is the number of coins in the ith pile.

Return the maximum number of coins which you can have.

Example:

Input: piles = [2,4,1,2,7,8]
Output: 9
Explanation: Choose the triplet (2, 7, 8), Alice Pick the pile with 8 coins, you the pile with 7 coins and Bob the last one.
Choose the triplet (1, 2, 4), Alice Pick the pile with 4 coins, you the pile with 2 coins and Bob the last one.
The maximum number of coins which you can have are: 7 + 2 = 9.
On the other hand if we choose this arrangement (1, 2, 8), (2, 4, 7) you only get 2 + 4 = 6 coins which is not optimal.

Input: piles = [2,4,5]
Output: 4

Input: piles = [9,8,7,6,5,1,2,3,4]
Output: 18

Constraints

• 3 <= piles.length <= 10^5
• piles.length % 3 == 0
• 1 <= piles[i] <= 10^4

풀이

코드

class Solution:
    def maxCoins(self, piles: List[int]) -> int:
        sortedPiles = sorted(piles, reverse=True)
        result = 0
        cnt = len(piles) / 3

        for i in range(len(piles)) :
            if not cnt : return result
            if i % 2 == 1 : 
                result += sortedPiles[i]
                cnt -= 1

결과

Runtime: 604 ms, faster than 47.83% of Python3 online submissions
Memory Usage: 26.6 MB, less than 18.05% of Python3 online submissions

설명

문제가 복잡하지만 결국 Alice는 내가 뽑은 3개 중에 가장 큰 애를 가져가고 나는 중간꺼, 그리고 Bob은 작은 거를 가져갔다. 이거를 없을 때까지 반복을 하게 된다. 개수가 3n이므로 n번 반복!

즉 나는 큰 순서대로 나열했을 때 가장 큰애를 빼고 다음으로 큰 애를 가져가는 게 제일 유리하다. 뽑을 때는 가장 큰 애, 그 다음 애, 가장 작은 애 이런 식으로 뽑게 된다. 그래서 내림차순으로 정렬했을 때 인덱스 1, 3 … 을 뽑는다. 다만 Bob꺼까지 더하지 않도록 처음 정해진 개수만큼만 더해서 리턴한다.