문제 개요
크기가 서로 다른 동전 더미가 총 3*n개 있다고 가정해 보겠습니다. 이 상태에서 세 명의 플레이어가 다음과 같은 규칙으로 게임을 진행합니다.
- 각 단계마다 플레이어1이 임의의 동전 더미 3개를 선택합니다.
- 플레이어2는 선택된 더미 중 동전이 가장 많은 것을 가져갑니다.
- 플레이어1은 그다음으로 많은 동전이 담긴 더미를 가져갑니다.
- 플레이어3은 마지막으로 남은 더미를 가져갑니다.
- 동전 더미가 모두 없어질 때까지 위 과정을 반복합니다.
정수 배열 piles가 주어지며, piles[i]는 i번째 더미에 들어 있는 동전의 개수를 의미합니다. 이때 플레이어1이 가질 수 있는 최대 동전 개수를 구하는 것이 목표입니다.
예시로 이해하기
입력이 piles = [2,4,1,2,7,8]인 경우를 살펴보겠습니다. 출력은 9가 됩니다.
- 먼저 트리플렛(2, 7, 8)을 선택하면, 플레이어2가 8을, 플레이어1이 7을, 플레이어3이 2를 가져갑니다.
- 다음으로 트리플렛(1, 2, 4)을 선택하면, 플레이어2가 4를, 플레이어1이 2를, 플레이어3이 1을 가져갑니다.
결과적으로 플레이어1은 7 + 2 = 9개의 동전을 확보하며, 이것이 가능한 최댓값입니다.
풀이 접근 방법
핵심은 그리디(Greedy) 전략입니다. 플레이어2는 항상 선택된 3개 중 가장 큰 값을 가져가므로, 플레이어1은 매 라운드에서 두 번째로 큰 값을 자신의 몫으로 만들어야 합니다. 따라서 정렬된 배열에서 가장 큰 값은 플레이어2에게, 두 번째로 큰 값은 플레이어1이 가져가고, 가장 작은 값을 플레이어3에게 희생시키는 것이 최적입니다. 구체적인 절차는 다음과 같습니다.
- 배열
piles를 오름차순으로 정렬합니다. - 결괏값을 저장할 변수
ans를 0으로 초기화합니다. - 배열이 빌 때까지 다음을 반복합니다.
ans에 뒤에서 두 번째 요소(현재 남은 것 중 두 번째로 큰 값)를 더합니다.- 뒤에서 두 번째 요소를 제거합니다.
- 마지막 요소(최댓값)를 제거합니다.
- 첫 번째 요소(최솟값)를 제거합니다.
ans를 반환합니다.
구현 코드
위 알고리즘을 파이썬으로 구현하면 다음과 같습니다.
def solve(piles):
piles.sort()
ans = 0
while(len(piles)!=0):
ans = ans + piles[-2]
del piles[-2]
del piles[-1]
del piles[0]
return ans
piles = [2,4,1,2,7,8]
print(solve(piles))입력
[2,4,1,2,7,8]
출력
9
복잡도 분석
정렬에 O(n log n)의 시간이 소요되고, 이후 각 라운드마다 3개씩 제거하므로 전체 시간 복잡도는 O(n log n), 공간 복잡도는 추가 배열을 사용하지 않으므로 O(1)입니다.