문제 개요
stones라는 배열이 주어지며, stones[i]는 왼쪽에서 i번째 돌의 가치를 나타냅니다. 두 플레이어 Amal과 Bimal이 이 돌들로 번갈아 진행하는 게임을 하며, 항상 Amal이 선공입니다. n개의 돌이 일렬로 놓여 있고, 각 플레이어는 자신의 차례에 줄의 가장 왼쪽 또는 가장 오른쪽에 있는 돌을 하나 제거한 뒤, 남아 있는 돌들의 가치 합만큼 점수를 얻습니다. 최종적으로 더 높은 점수를 기록한 플레이어가 승리합니다.
Bimal은 자신이 이 게임에서 필패라는 사실을 깨닫고, 지더라도 점수 차이를 최소화하는 방향으로 플레이하기로 결정했습니다. 반대로 Amal의 목표는 점수 차이를 최대화하는 것입니다. 두 사람이 모두 최선을 다해 플레이할 때, Amal과 Bimal의 점수 차이를 구하는 것이 우리의 과제입니다.
예시로 이해하기
입력이 stones = [6, 4, 2, 5, 3]이라면 정답은 8입니다. 진행 과정을 단계별로 살펴보겠습니다.
- 1단계: Amal이 오른쪽 끝의 3을 제거 → 남은 돌 [6, 4, 2, 5], 합계 17점 → Amal 누적 17점
- 2단계: Bimal이 왼쪽 끝의 6을 제거 → 남은 돌 [4, 2, 5], 합계 11점 → Bimal 누적 11점
- 3단계: Amal이 4를 제거 → 남은 돌 [2, 5], 합계 7점 → Amal 누적 17 + 7 = 24점
- 4단계: Bimal이 2를 제거 → 남은 돌 [5], 합계 5점 → Bimal 누적 11 + 5 = 16점
- 5단계: Amal이 마지막 돌 5를 제거 → 남은 돌이 없으므로 0점 → Amal 최종 24점
따라서 두 사람의 점수 차이는 24 − 16 = 8이 됩니다.
풀이 접근 방식
이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 "특정 부분 배열에서 얻을 수 있는 최적의 점수 차이"를 dp 배열에 저장하는 것입니다.
부분 배열 stones[i..j]를 고려할 때 현재 차례의 플레이어에게는 두 가지 선택지가 있습니다.
- 오른쪽 끝 돌 stones[j]를 제거하는 경우: 제거자는 남은 돌들의 합(run_sum + v)만큼 점수를 얻고, 상대는 구간 [i..j−1]에서 최적으로 플레이하므로 dp[j−1]을 빼주어야 합니다.
- 왼쪽 끝 돌 stones[i]를 제거하는 경우: 제거자는 남은 돌들의 합(new_run)만큼 점수를 얻고, 상대는 구간 [i+1..j]에서 최적으로 플레이하므로 dp[j]를 빼주어야 합니다.
두 선택 중 더 큰 값을 dp[j]에 저장하고, 최종적으로 dp[n−1]이 전체 배열에 대한 최적 점수 차이가 됩니다. 시간 복잡도는 O(n²)입니다.
알고리즘 단계
- n := stones의 크기
- dp := 크기가 n인 배열, 0으로 초기화
- i를 n−1부터 0까지 감소시키며 반복:
- v := stones[i]
- run_sum := 0
- j를 i+1부터 n−1까지 반복:
- new_run := run_sum + stones[j]
- dp[j] := max(new_run − dp[j], run_sum + v − dp[j−1])
- run_sum := new_run
- dp[n−1] 반환
구현 예시
다음 구현을 통해 더 잘 이해해 보겠습니다.
def solve(stones):
n = len(stones)
dp = [0] * n
for i in range(n - 1, -1, -1):
v = stones[i]
run_sum = 0
for j in range(i + 1, n):
new_run = run_sum + stones[j]
dp[j] = max(new_run - dp[j], run_sum + v - dp[j - 1])
run_sum = new_run
return dp[n - 1]
stones = [6, 4, 2, 5, 3]
print(solve(stones))입력
[6, 4, 2, 5, 3]
출력
8