Divisor Game

앨리스와 밥이 차례로 게임을 합니다. 앨리스가 먼저 시작합니다.

처음에는 칠판에 숫자 n 이 적혀 있습니다. 각 플레이어의 차례가 되면, 다음과 같은 이동을 수행합니다:

• 0 < x < n 이고 n \% x == 0 인 임의의 x 를 선택합니다.
• 칠판에 적힌 숫자 n 을 n - x 로 대체합니다.
• 또한, 플레이어가 이동할 수 없는 경우, 그 플레이어는 게임에서 패배합니다.

두 플레이어가 최적의 플레이를 한다고 가정했을 때, 앨리스가 게임에서 승리하는 경우에만 true를 반환하세요.

예제 1:

입력: n = 2

출력: true

설명: 앨리스가 1을 선택하고, 밥은 더 이상 이동할 수 없습니다.

예제 2:

입력: n = 3

출력: false

설명: 앨리스가 1을 선택하고, 밥이 1을 선택하면, 앨리스는 더 이상 이동할 수 없습니다.

제약 조건:

1 <= n <= 1000

문제풀이

class Solution:
   def divisorGame(self, n: int) -> bool:
       dp = [False] * (n + 1)
       
       dp[1] = False

       for i in range(2, n + 1):
           for x in range(1, i):
               if i % x == 0 and not dp[i - x]:
                   dp[i] = True
                   break

       return dp[n]

<내 코드의 흐름>

1. divisorGame이라는 메서드를 정의합니다.

• 이 메서드는 정수 n을 입력으로 받아 bool 타입의 값을 반환합니다.

2. dp라는 배열을 생성합니다. 이 배열은 크기가 n + 1이고, 모든 요소는 False로 초기화됩니다.

• dp[i]는 i에서 시작하는 플레이어가 이길 수 있는지를 나타냅니다.

3. 기본 케이스를 설정합니다. n이 1인 경우, 플레이어는 이동할 수 없으므로 패배합니다.

• 따라서 dp[1]은 False입니다.

4. 2부터 n까지의 모든 값에 대해 dp 테이블을 채웁니다.
5. 1부터 i-1까지의 모든 x에 대해 검사합니다.
6. i % x == 0 조건을 만족하고, dp[i - x]가 False인 경우를 찾습니다.

• 이는 현재 i가 x로 나누어 떨어지며, i - x에서 시작하는 상대방이 패배하는 경우를 의미합니다.

7. 위 조건을 만족하면 dp[i]를 True로 설정하고, 더 이상의 검사를 중단합니다. * 이는 현재 플레이어가 이길 수 있음을 의미합니다.
8. dp[n]의 값을 반환합니다.

• 이는 주어진 n에서 시작하는 앨리스의 승리 여부를 나타냅니다.