Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 푸는 스톤 게임 문제 – 동적 계획법으로 최적의 해 찾기

두 명의 플레이어 Alex와 Lee가 여러 개의 돌 무더기를 놓고 게임을 진행하는 상황을 생각해 보겠습니다. 돌 무더기는 짝수 개수로 일렬로 배치되어 있으며, 각 무더기에는 piles[i]개의 돌이 들어 있습니다.

게임 규칙

  • 게임의 목표는 게임이 끝났을 때 가장 많은 돌을 가지는 것입니다.
  • 전체 돌의 개수가 홀수이므로 무승부는 존재하지 않습니다.
  • Alex와 Lee는 번갈아 가며 차례를 진행하고, Alex가 항상 먼저 시작합니다.
  • 각 차례에 플레이어는 일렬로 된 돌 무더기 중 맨 앞 또는 맨 뒤에 있는 무더기 전체를 가져가야 합니다.
  • 모든 무더기가 소진될 때까지 반복되며, 가장 많은 돌을 가진 사람이 승리합니다.

Alex와 Lee가 모두 최적의 전략으로 플레이한다고 가정할 때, Alex가 이 게임에서 승리하는지 판단하는 것이 우리의 과제입니다.

예시로 살펴보기

입력이 [5, 3, 4, 5]라고 가정해 보겠습니다. 이 경우 결과는 true입니다.

Alex가 먼저 시작하기 때문에 선택할 수 있는 것은 첫 번째 5 또는 마지막 5뿐입니다.

  • 첫 번째 5를 가져가는 경우: 남은 배열은 [3, 4, 5]가 됩니다.
    • Lee가 3을 가져가면 → 보드는 [4, 5]가 되고, Alex가 5를 가져가 10점으로 승리합니다.
    • Lee가 마지막 5를 가져가면 → 보드는 [3, 4]가 되고, Alex가 4를 가져가 9점으로 승리합니다.

즉, 첫 번째 5를 가져가는 것이 Alex의 승리 전략이므로 답은 true입니다.

풀이 접근 방식

이 문제는 구간 기반 동적 계획법(DP)으로 해결할 수 있습니다. 아래 순서대로 진행합니다.

  1. n := piles 배열의 크기로 설정합니다.
  2. n × n 크기의 dp 행렬과, n + 1 크기의 pre 배열(누적 합 배열)을 생성합니다.
  3. i를 0부터 n − 1까지 반복하면서 누적 합을 계산합니다.
    • pre[i + 1] := pre[i] + piles[i]
  4. 구간 길이 l을 2부터 n까지 늘려가며 다음을 수행합니다.
    • i := 0, j := l − 1로 시작하고, j < n인 동안 i와 j를 1씩 증가시키며 반복합니다.
    • dp[i][j] := max(piles[j] + pre[j] − pre[i] − dp[i][j − 1],  piles[i] + pre[i + 2] − pre[j] + dp[i + 1][j])
  5. dp[0][n − 1] > dp[0][n − 1] − pre[n]이 성립하면 true를 반환합니다.

여기서 pre 배열은 특정 구간의 돌 총합을 빠르게 구하기 위한 누적 합(prefix sum)이며, dp 값은 해당 구간에서 선공이 확보할 수 있는 최적 결과를 나타냅니다.

C++ 구현 코드

아래 구현 예시를 통해 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool stoneGame(vector<int>& piles) {
      int n = piles.size();
      vector < vector <int> > dp(n,vector <int>(n));
      vector <int> pre(n + 1);
      for(int i = 0; i < n; i++){
         pre[i + 1] = pre[i] + piles[i];
      }
      for(int l = 2; l <= n; l++){
         for(int i = 0, j = l - 1; j < n; i++, j++){
            dp[i][j] = max(piles[j] + pre[j] - pre[i] - dp[i][j - 1], piles[i] + pre[i + 2] - pre[j] +             dp[i       + 1][j]);
         }
      }
      return dp[0][n - 1] > dp[0][n - 1] - pre[n];
   }
};
main(){
   vector<int> v = {5,3,4,5};
   Solution ob;
   cout << (ob.stoneGame(v));
}

입력

[5,3,4,5]

출력

1