Python에서 Amal이 돌 게임에서 이길 수 있는지 확인하는 프로그램

<시간/>

Amal과 Bimal 두 명의 플레이어가 게임을 하고 있고 Amal이 먼저 시작한다고 가정합니다. 처음에는 더미에 n개의 서로 다른 돌이 있습니다. 각 플레이어의 차례에 그는 더미에서 0이 아닌 정사각형의 돌을 제거하는 이동을 합니다. 또한 한 플레이어가 움직일 수 없으면 게임에서 집니다. 따라서 n이 있으면 Amal이 게임에서 이길 수 있는지 여부를 확인해야 합니다.

따라서 입력이 n =21과 같으면 처음에 Amal이 16을 취하고 Bimal이 4를 취한 다음 Amal이 1을 취하여 게임에서 승리하기 때문에 출력은 True가 됩니다.

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

사각형 :=새 목록
정사각형 :=1
증가 :=3
동안 정사각형 <=n, 수행
- 사각형 끝에 사각형 삽입
- 정사각형 :=정사각형 + 증가
- 증가 :=증가 + 2
사각형 끝에 사각형 삽입
dp :=크기의 빈 목록(n + 1)
dp[0] :=거짓
범위 1에서 n까지의 k에 대해 수행
- s :=0
- dp[k] :=거짓
- squares[s] <=k 및 dp[k]가 비어 있는 동안 do
  - dp[k - squares[s]]가 비어 있으면
    - dp[k] :=참
  - s :=s + 1
dp의 마지막 요소를 반환

예

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

def solve(n):
   squares = []
   square = 1
   increase = 3
   while square <= n:
      squares.append(square)
      square += increase
      increase += 2
   squares.append(square)

   dp = [None] * (n + 1)
   dp[0] = False
   for k in range(1, n + 1):
      s = 0
      dp[k] = False
      while squares[s] <= k and not dp[k]:
         if not dp[k - squares[s]]:
            dp[k] = True
         s += 1
   return dp[-1]

n = 21
print(solve(n))

입력

출력

True