C++에서 승자 예측

<시간/>

음이 아닌 정수인 점수 배열이 있다고 가정합니다. 첫 번째 플레이어는 배열의 양쪽 끝에서 숫자 중 하나를 선택한 다음 두 번째 플레이어, 첫 번째 플레이어 등의 순서로 숫자 중 하나를 선택합니다. 플레이어가 번호를 선택할 때마다 다른 플레이어는 해당 번호를 사용할 수 없습니다. 이것은 모든 점수가 선택될 때까지 계속됩니다. 최대 점수를 얻은 플레이어가 승리합니다. 따라서 점수 배열이 있는 경우 플레이어 1이 승자인지 예측해야 합니다.

따라서 입력이 [1, 5, 233, 7]과 같으면 첫 번째 플레이어가 1을 선택했으므로 출력은 True가 됩니다. 그런 다음 두 번째 플레이어는 5와 7 중 하나를 선택해야 합니다. 두 번째 숫자에 상관없이 플레이어가 선택하면 첫 번째 플레이어는 233을 선택할 수 있습니다. 마지막으로 첫 번째 플레이어는 두 번째 플레이어(12)보다 더 많은 점수(234)를 가지고 있으므로 첫 번째 플레이어가 이길 수 있으므로 true를 반환해야 합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n이 1과 같으면 -
- true를 반환
크기가 n x n인 배열 player1, 크기가 n x n인 배열 player2 및 크기 n x n의 합을 정의합니다.
initialize i :=0의 경우, i
- j 초기화의 경우:=0, j
  - 플레이어1[i, j] :=-1
  - 플레이어2[i, j] :=-1
initialize i :=0의 경우, i
- 초기화 j :=i의 경우 j
  - i가 j와 같으면 -
    - 합계[i, j] :=arr[i]
  - 그렇지 않으면
    - 합계[i, j] :=arr[j] + 합계[i, j - 1]
길이 초기화:=1의 경우 길이 <=n일 때 업데이트(길이를 1만큼 증가), 수행 -
- initialize i :=0의 경우 i + length - 1
  - 끝 :=i + 길이 - 1
  - i + 1 <=끝이면 -
    - player1[i, end] :=최대 arr[i] + ((player2[i + 1, end]가 -1과 같으면 0이고 그렇지 않으면 player2[i + 1, end])) 및 arr[end ] + ((player2[i, end - 1]이 -1과 같으면 , 그렇지 않으면 player2[i, end - 1]))
  - 그렇지 않으면
    - player1[i, end] :=arr[i]
  - player2[i, end] :=sum[i, end] - player1[i, end]
player1[0, n - 1]>=player2[0, n - 1]이면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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}