1561-kir3i.md

1561. Maximum Number of Coins You Can Get

Solution

• 시간복잡도: O(NlogN), 정렬의 시간복잡도와 동일

• 알고리즘

  구현

• 풀이설명

  piles에는 3n개의 pile에 대한 정보가 기록되어 있습니다. 이 때 문제에서 주어진 규칙에 따르면 '나'가 코인을 최대로 가져올 수 있는 경우는 다음과 같습니다.

  1. Bob이 piles의 모든 pile 중 크기가 작은 것부터 차례로 n개를 가져갑니다.
  2. 남은 pile을 큰 순으로 정렬하고 Alice부터 '나'와 번갈아가면서 하나씩 차례로 갖고 옵니다.

  위 규칙대로 구현해서 '나'가 얻을 수 있는 코인의 합을 구하면 됩니다.

• 소스코드

  • C++

    class Solution {
    public:
        int ans = 0;
        int maxCoins(vector<int>& piles) {
            sort(piles.begin(), piles.end());
            int sz = piles.size();
            for(int i=sz/3; i<sz; i+=2)
                ans += piles[i];
            return ans;
        }
    };

  • Python

    class Solution:
        def maxCoins(self, piles):
            return sum(sorted(piles, reverse=True)[1:2*len(piles)//3:2])