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

1. Input

1) 3n개의 음이 아닌 정수를 담은 int 배열 piles

2) piles[i]는 동전 더미이며, piles[i]의 값은 동전의 개수를 나타낸다.

3) 나를 포함한 3명이 동전을 나눠가질 예정이다.

4) 내가 3n개의 동전 더미 중 3개를 골랐을 때, 셋 중 동전의 개수가 2번째로 많은 더미를 가져갈 것이다.

 

2. Output

1) 내가 최대한으로 가져갈 수 있는 동전의 개수를 담은 int 변수 max

2) 동전 더미는 남는 것 없이 모두 가져가야 한다.

 

3. Constraint

1) 3 <= piles.length <= 105

2) piles.length % 3 == 0

3) 1 <= piles[i] <= 104

 

4. Example

Input: piles = {2,4,1,2,7,8}
Output: 9

설명:

  - 처음에 (2,7,8)을 고르면, 나는 7개를 가져갈 수 있다. 그다음 (2,4,1)을 고르면, 나는 2개를 가져갈 수 있다. -> 9개

  - 처음에 (4,1,8)를 고르면, 나는 4개를 가져갈 수 있다. 그다음 (2,2,7)을 고르면, 나는 2개를 가져갈 수 있다. -> 6개

  - 어떻게 해도 9개보다 많은 동전을 가져갈 수는 없다.

 

5. Code

1) 첫 코드(2022/08/19)

Arrays.sort(piles);
int max = 0;
for(int i=piles.length/3 ; i<piles.length ; i+=2)
    max += piles[i];
return max;

  - piles를 크기 순으로 정렬한다.

  - 내가 고른 것이 (a,b,c)이고 a<b<c일 때, b만 가져가므로 a에 들어갈 수 있는 동전 더미는 piles[0]~piles[n -1]에서 할당해주면 된다.

  - 남은 2n개의 더미들 중 내가 최대로 많이 가져가려면

    - c에 들어가는 것: piles[3n-1], piles[3n-3], ..., piles[n+1]

    - b에 들어가는 것: piles[3n-2], piles[3n-4], ..., piles[n]

  - 따라서 n번째부터 1개씩 건너뛰면서 더해주면 된다.