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

1561. Maximum Number of Coins You Can Get

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

Maximum Number of Coins You Can Get - LeetCode

 

[ 문제 풀이 ]

이번에도 문제 파악하는데 시간이 많이 소요되었다. 여러 숫자가 섞인 3n개의 동전 더미에서 내가 선택할 수 있는 수 중 가장 최대 합을 구하는 문제이다. 문제의 조건은 다음과 같다.

- 각 단계에서 3개의 동전 더미 선택(연속적일 필요는 없음)

- 3개의 동전 더미에서 Alice는 가장 최대 수를 고를 것이다.

- 나는 그 다음 최대 수를 고를 것이다.

- Bob이 마지막 것을 고를 것이다.

 

처음엔 문제가 잘 이해되지 않아 sorting 한 후 중복되는 수는 다시 자리를 바꾸고, 3n개씩 잘라 그 중 가운데 수를 누적하는 방식으로 구성했다. 하지만 생각해보니, [9, 8, 7, 6, 5, 1, 2, 3, 4]일 때 정렬를 하면 [9, 8, 7,  6, 5, 4, 3, 2, 1]이 되고, 그 중 가운데 수만 모두 합하면 [8, 5, 2]의 합 15가 최댓값이 된다. [9, 8, 1], [7, 6, 2], [5, 4, 3]으로 나누면 [8, 6, 4] 즉 18이 최댓값이 된다.

따라서 아래 코드와 같이 정렬 후 [9, 8, 7, 6, 5, 4] (인덱스 5)까지만 반복되도록 범위를 설정하고 짝수 번호의 인덱스만 result에 누적하여 더해주었다.

 

 

[ 코드 ]

/**
 * @param {number[]} piles
 * @return {number}
 */
const maxCoins = function (piles) {
  const sorted = piles.slice().sort((a, b) => b - a);
  let result = 0;

  for (let i = 0; i < sorted.length - sorted.length / 3; i += 2) {
    result += sorted[i + 1];
  }

  return result;
};

// maxCoins([9, 8, 7, 6, 5, 1, 2, 3, 4]);
// output: 18