[LeetCode] 1561. Maximum Number of Coins You Can Get

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

Maximum Number of Coins You Can Get - LeetCode

leetcode - Maximum Number of Coins You Can Get

문제 유형 : 배열, 구현, 정렬

문제 난이도 : Medium

 

문제

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 the 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 that you can have.

 

3n개의 다양한 개수의 코인을 담는 조각들이 있다. 당신과 당신의 친구들은 다음의 규칙으로 조각을 가져갈 것이다.

1. 각 스텝에서, 당신은 조각들 중에서 3개의 조각을 고른다. 이 조각들끼리 인접할 필요는 없다.

2. 당신이 고르고 나면, Alice는 가장 큰 조각을 가져간다.

3. 당신은 그 다음으로 큰 조각을 가져간다.

4. 당신의 친구 Bob이 마지막 조각을 가져간다.

5. 코인이 안 남을때까지 반복한다.

 

정수 배열 piles가 주어진다. 당신이 얻을 수 있는 최대의 코인의 수를 구하시오.

 

 

 

풀이

 

3개씩 쌍을 지을 때, Alice가 반드시 가장 큰 수를 가져가고, 나는 그 다음으로 큰 수를 얻는다.

여기서 중요한 건, Bob에게는 최소한의 수를 줘야 한다는 것이다.

 

매 라운드마다 쌍을 다음과 같이 지어주면 된다: (가장 큰 수, 그 다음으로 큰 수, 제일 작은 수)

내림차순으로 요소를 정렬시키고, 배열의 2/3지점까지의 홀수 인덱스들의 수들을 누적시키면 해결된다.

 

 

코드

C++

class Solution {
public:
    int maxCoins(vector<int>& piles) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        
        int sum = 0;
        sort(piles.begin(), piles.end(), greater<int>());

        for(int i = 0; i < piles.size()*2/3; i+=2) {
            sum += piles[i+1];
        }

        return sum;
    }
};