Amal과 Bimal이 돌 무더기를 가지고 게임을 하고 있습니다. 여러 개의 돌이 한 줄로 나열되어 있으며, 각 돌에는 stoneValue 배열에 주어진 숫자 값이 매겨져 있습니다.
두 사람은 번갈아 가며 차례를 진행하며, Amal이 먼저 시작합니다. 각 차례마다 플레이어는 줄 맨 앞에 남아 있는 돌 중에서 1개, 2개 또는 3개를 가져갈 수 있습니다.
각 플레이어의 점수는 자신이 가져간 돌 값들의 합이며, 초기 점수는 0입니다. 게임의 목표는 최대한 높은 점수로 마무리하는 것이고, 가장 높은 점수를 얻은 플레이어가 승자가 되며 두 사람의 점수가 같으면 무승부가 됩니다. 게임은 모든 돌이 사라질 때까지 계속됩니다.
여기서 Amal과 Bimal은 모두 최선의 전략으로 게임을 진행한다고 가정합니다. 우리는 Amal이 이기면 "Amal", Bimal이 이기면 "Bimal", 동점이면 "Tie"를 반환해야 합니다.
예를 들어 입력이 values = [1,2,3,7]이라면 출력은 Bimal입니다. Amal은 어떻게 움직여도 이길 수 없는데, 그의 최선의 수인 3개의 돌을 모두 가져가도 점수는 6에 불과하고, 이후 Bimal이 값 7의 돌을 가져가 승리하게 됩니다.
동적 계획법(DP)을 이용한 접근 방법
이 문제는 게임형 DP(미니맥스) 기법으로 해결할 수 있습니다. dp[i]를 "i번째 돌부터 시작했을 때 현재 차례인 플레이어가 얻을 수 있는 최대 점수"라고 정의하면, 상대방이 이후 얻게 될 최대 점수를 고려하는 방식으로 점화식을 세울 수 있습니다.
- 크기가 n + 10인 배열
dp와sum을 선언하고,dp의 모든 값을 매우 작은 값(-10^9)으로 초기화합니다. sum[n-1] = v[n-1]로 설정한 뒤, 뒤에서 앞으로 순회하며sum[i] = sum[i+1] + v[i]로 누적합을 계산합니다. 즉,sum[i]는 i번째 돌부터 마지막 돌까지의 값 합입니다.- i를 n-1부터 0까지 역순으로 순회하면서, 각 위치에서 가져갈 수 있는 돌의 개수 k(i+1부터 i+3까지, 단 k ≤ n)에 대해 다음 점화식을 적용합니다.
dp[i] = max(dp[i], sum[i] - dp[k]) - 전체 합
total = sum[0], Amal의 점수x = dp[0], Bimal의 점수y = total - x를 계산합니다. - x > y이면 "Amal", x == y이면 "Tie", 그렇지 않으면 "Bimal"을 반환합니다.
핵심 아이디어는 다음과 같습니다. 현재 플레이어가 i번째부터 k-1번째까지 돌을 가져가면, 상대방은 k번째부터 최적으로 플레이하여 dp[k]만큼의 점수를 얻습니다. 따라서 현재 플레이어의 총 점수는 (sum[i] - sum[k]) + (sum[k] - dp[k]) = sum[i] - dp[k]가 되며, 이 값이 최대가 되도록 k를 선택하면 됩니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string stoneGameIII(vector<int>& v) {
int n = v.size();
vector<int> dp(n + 10);
vector<int> sum(n + 10);
for(int i = 0; i < n; i++)dp[i] = -1e9;
sum[n - 1] = v[n - 1];
for(int i = n - 2; i >= 0; i--)sum[i] = sum[i + 1] + v[i];
for(int i = n- 1 ; i >= 0; i--){
for(int k = i + 1; k <= i + 3 && k <= n; k++){
dp[i] = max(dp[i], sum[i] - dp[k]);
}
}
int total = sum[0];
int x = dp[0];
int y = total - x;
return x > y? "Amal" : x == y ? "Tie" : "Bimal";
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,7};
cout << (ob.stoneGameIII(v));
}
입력
{1,2,3,7}
출력
Bimal