Python으로 세 개의 돌더미에서 최대 점수 구하는 프로그램

문제 개요

세 개의 값 a, b, c가 주어져 있다고 가정해 봅시다. 우리는 크기가 각각 a, b, c인 세 개의 돌더미로 솔리테어 게임을 진행합니다. 매 턴마다 플레이어는 서로 다른 두 개의 비어 있지 않은 더미를 골라 각각에서 돌을 하나씩 꺼내고, 점수에 1점을 추가합니다. 비어 있지 않은 더미가 2개 미만으로 남으면 게임이 종료됩니다. 이때 얻을 수 있는 최대 점수를 구하는 것이 목표입니다.

예를 들어 입력이 a = 4, b = 4, c = 6이라면 출력은 7이 됩니다. 초기 상태는 (4, 4, 6)이며, 다음과 같은 순서로 진행할 수 있습니다.

1번째와 2번째 더미에서 선택 → 현재 상태 (3, 3, 6)
1번째와 3번째 더미에서 선택 → 현재 상태 (2, 3, 5)
1번째와 3번째 더미에서 선택 → 현재 상태 (1, 3, 4)
1번째와 3번째 더미에서 선택 → 현재 상태 (0, 3, 3)
2번째와 3번째 더미에서 선택 → 현재 상태 (0, 2, 2)
2번째와 3번째 더미에서 선택 → 현재 상태 (0, 1, 1)
2번째와 3번째 더미에서 선택 → 현재 상태 (0, 0, 0)

마지막에는 비어 있지 않은 더미가 2개 미만이므로 게임이 종료되며, 총 7점을 얻게 됩니다.

핵심 아이디어

획득 가능한 점수에는 두 가지 자연스러운 상한이 존재합니다. 첫째, 한 번의 행동마다 돌이 2개씩 사라지므로 전체 점수는 전체 돌 수의 절반을 넘을 수 없습니다. 둘째, 가장 큰 더미 하나만 남겨두고는 점수를 낼 수 없으므로, 점수는 두 작은 더미의 돌 수 합을 넘을 수 없습니다. 이 두 상한을 활용하면 문제를 간단한 수식으로 해결할 수 있습니다.

해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

minimum := a, b, c 중 최솟값
maximum := a, b, c 중 최댓값
left := a + b + c − maximum − minimum (중간값)
만약 maximum − left ≤ minimum이라면, minimum + left − (1 + minimum − (maximum − left)) // 2를 반환
그렇지 않으면 minimum + min(maximum − minimum, left)를 반환

예제 코드

아래 구현을 통해 더 잘 이해해 봅시다.

def solve(a, b, c):
   minimum = min(a, b, c)
   maximum = max(a, b, c)
   left = a + b + c - maximum - minimum
   if maximum - left <= minimum:
      return minimum + left - (1 + minimum - (maximum - left)) // 2
   return minimum + min(maximum - minimum, left)

a = 4
b = 4
c = 6
print(solve(a, b, c))

입력

4, 4, 6