앨리스와 밥 두 사람이 한 줄로 놓인 돌 무더기를 가지고 게임을 계속 이어가고 있습니다. 각 무더기에는 양의 정수 개수의 돌이 들어 있으며, 배열 piles[i]로 표현됩니다. 게임의 목표는 가능한 한 많은 돌을 확보하는 것입니다. 앨리스와 밥은 번갈아 가며 차례를 진행하며, 항상 앨리스가 먼저 시작합니다. 초기값은 M = 1입니다.
각 플레이어는 자신의 차례에 남아 있는 첫 번째 X개의 무더기에 있는 모든 돌을 가져갈 수 있으며, 이때 1 <= X <= 2M 조건을 만족해야 합니다. 그런 다음 M = max(M, X)로 갱신됩니다. 더 이상 남은 돌이 없으면 게임이 종료됩니다.
예를 들어 piles = [2,7,9,4,4]라면 출력은 10이 됩니다. 앨리스가 처음에 한 무더기를 가져가면 밥이 두 무더기를 가져가고, 다시 앨리스가 두 무더기를 가져가는 방식입니다. 이 경우 앨리스는 2 + 4 + 4 = 10개의 돌을 손에 넣게 됩니다. 반면 앨리스가 처음에 두 무더기를 가져가면 밥이 남은 세 무더기를 모두 가져갈 수 있으므로, 앨리스는 2 + 7 = 9개만 얻게 됩니다. 따라서 더 큰 값인 10을 반환합니다.
문제 해결 접근 방법
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- 배열 arr, 인덱스 i, 값 m, 그리고 dp 행렬을 인자로 받는 재귀 함수 solve를 생성합니다.
- i >= arr의 크기이면 0을 반환합니다.
- dp[i][m]이 -1이 아니면(즉, 이미 계산된 값이면) dp[i][m]을 반환합니다.
- i - 1 + 2m >= 배열의 크기이면 arr[i]를 반환합니다. 즉, 남은 모든 무더기를 한 번에 가져갈 수 있는 상황입니다.
- op := 무한대(inf)로 초기화합니다.
- x를 1부터 2m까지 순회하면서 op := min(op, solve(arr, i + x, max(x, m), dp))로 갱신합니다. 이는 상대방이 가져갈 수 있는 최소값을 의미합니다.
- dp[i][m] := arr[i] - op로 설정하고 반환합니다.
실제 구현 절차
- n := piles 배열의 크기로 설정하고, 크기 n의 배열 arr을 생성합니다.
- arr[n - 1] := piles[n - 1]로 초기화합니다.
- i를 n - 2부터 0까지 역순으로 순회하며 arr[i] := arr[i + 1] + piles[i]로 설정합니다. 이렇게 하면 arr[i]는 i번째부터 끝까지의 누적 합이 됩니다.
- 크기가 (n + 1) × (n + 1)인 행렬을 생성하고 모든 값을 -1로 채웁니다.
- solve(arr, 0, 1, dp)를 반환합니다.
아래 예시 코드를 통해 더 잘 이해할 수 있습니다.
예시 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void printVector(vector <int> v){
for(int i =0;i<v.size();i++)cout << v[i] << " ";
cout << endl;
}
int stoneGameII(vector<int>& piles) {
int n = piles.size();
vector <int> arr(n);
arr[n-1] = piles[n-1];
for(int i = n-2;i>=0;i--)arr[i] = arr[i+1] + piles[i];
vector < vector <int> > dp(n+1,vector <int> (n+1,-1));
return solve(arr,0,1,dp);
}
int solve(vector <int> arr, int i, int m, vector < vector <int> > &dp){
if(i >=arr.size())return 0;
if(dp[i][m]!=-1)return dp[i][m];
if(i-1+2*m >=arr.size())return arr[i];
int opponentCanTake = INT_MAX;
for(int x =1;x<=2*m;x++){
opponentCanTake = min(opponentCanTake,solve(arr,i+x,max(x,m),dp));
}
dp[i][m] = arr[i] - opponentCanTake;
return dp[i][m];
}
};
main(){
vector<int> v = {2,7,9,4,4};
Solution ob;
cout <<(ob.stoneGameII(v));
}입력
[2,7,9,4,4]
출력
10
이 알고리즘은 뒤에서부터의 누적 합(prefix sum)과 메모이제이션을 활용한 동적 계획법(DP)으로 동작하므로, 시간 복잡도는 O(n²) 수준으로 효율적으로 문제를 해결할 수 있습니다.