문제 소개
음이 아닌 정수(non-negative integer)로 구성된 점수 배열이 하나 주어집니다. 첫 번째 플레이어가 배열의 양쪽 끝에 있는 숫자 중 하나를 선택하면, 이어서 두 번째 플레이어가 남은 숫자의 양쪽 끝에서 하나를 선택하고, 두 플레이어가 번갈아 가며 이 과정을 반복합니다. 한 번 선택된 숫자는 상대방이 다시 사용할 수 없으며, 모든 점수가 선택될 때까지 게임이 진행됩니다. 최종적으로 더 높은 점수를 얻은 플레이어가 승리합니다. 우리가 해야 할 일은 주어진 점수 배열에서 첫 번째 플레이어가 반드시 이길 수 있는지를 예측하는 것입니다.
예를 들어 입력이 [1, 5, 233, 7]이라면 출력은 True입니다. 첫 번째 플레이어가 1을 선택하면 두 번째 플레이어는 5와 7 중에서만 고를 수 있습니다. 어느 쪽을 선택하든 그다음 차례에 첫 번째 플레이어는 반드시 233을 가져올 수 있습니다. 결과적으로 첫 번째 플레이어는 234점(1 + 233), 두 번째 플레이어는 12점(5 + 7)을 얻게 되므로, 첫 번째 플레이어가 확실하게 승리한다는 뜻으로 true를 반환하면 됩니다.
해결 전략
이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 풀 수 있습니다. 핵심 아이디어는 각 구간 [i, j]에 대해 선공 플레이어(player1)와 후공 플레이어(player2)가 각각 얻을 수 있는 최대 점수를 미리 계산해 두는 것입니다. 알고리즘의 단계별 흐름은 다음과 같습니다.
기저 사례 처리: n이 1이라면 원소가 하나뿐이므로 첫 번째 플레이어가 무조건 그 숫자를 가져가게 됩니다. 따라서 즉시 true를 반환합니다.
크기 n × n의 세 개 배열
player1,player2,sum을 선언하고, 모든 값을 -1로 초기화합니다(-1은 아직 계산되지 않았음을 나타냅니다).구간 합 계산: sum[i][j]에는 인덱스 i부터 j까지의 원소 합을 저장합니다. i == j일 때는 arr[i] 그대로, 그 외에는 arr[j] + sum[i][j-1]로 누적 계산합니다.
구간 길이 확장: 구간 길이(length)를 1부터 n까지 늘려가며 각 구간 [i, end]에 대해 다음을 수행합니다.
player1[i][end] = max(arr[i] + player2[i+1][end], arr[end] + player2[i][end-1]) — 왼쪽 끝을 선택했을 때와 오른쪽 끝을 선택했을 때의 기대 점수를 비교해 더 큰 값을 저장합니다.
player2[i][end] = sum[i][end] − player1[i][end] — 구간 전체 합에서 선공의 점수를 빼면 후공의 점수가 됩니다.
최종 판정: player1[0][n-1] ≥ player2[0][n-1]이면 true, 아니면 false를 반환합니다.
참고로 이 문제는 리트코드(LeetCode) 486번 'Predict the Winner'와 동일한 유형이며, 시간 복잡도와 공간 복잡도 모두 O(n²)로 배열 크기에 대해 다항 시간 내에 해결됩니다.
구현 예제
아래는 위 알고리즘을 C++로 구현한 전체 코드입니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
lli solve(vector <int> arr, lli n){
if (n == 1)
return true;
lli player1[n][n], player2[n][n], sum[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
player1[i][j] = -1;
player2[i][j] = -1;
}
}
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (i == j) {
sum[i][j] = arr[i];
}
else {
sum[i][j] = arr[j] + sum[i][j - 1];
}
}
}
for (int length = 1; length <= n; length++) {
for (int i = 0; i + length - 1 < n; i++) {
lli end = i + length - 1;
if (i + 1 <= end)
player1[i][end] = max(arr[i] + (player2[i + 1][end] == -1 ? 0 : player2[i + 1][end]), arr[end] + (player2[i][end - 1] == -1 ?: player2[i][end - 1]));
else
player1[i][end] = arr[i];
player2[i][end] = sum[i][end] - player1[i][end];
}
}
return player1[0][n - 1] >= player2[0][n - 1];
}
bool PredictTheWinner(vector<int>& nums) {
return solve(nums, nums.size()) ;
}
};
main(){
Solution ob;
vector<int> v = {1, 5, 233, 7};
cout << (ob.PredictTheWinner(v));
}
입력
{1, 5, 233, 7}
출력
1
마무리
이처럼 구간 단위로 선공과 후공의 최적 점수를 동시에 추적하면, 매번 최선의 선택을 하는 두 플레이어 간의 대국 결과를 정확하게 예측할 수 있습니다. 같은 패턴의 문제(예: 돌 게임, 카드 더미 나누기 등)에도 응용할 수 있으니, 구간 DP의 기본 골격을 익혀 두면 다양한 게임 이론 문제를 해결하는 데 큰 도움이 됩니다.