[LeetCode] #1025. Divisor Game - Python

1. 문제

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there is a number N on the chalkboard.  On each player's turn, that player makes a move consisting of:

• Choosing any x with 0 < x < N and N % x == 0.
• Replacing the number N on the chalkboard with N - x.

Also, if a player cannot make a move, they lose the game.

Return True if and only if Alice wins the game, assuming both players play optimally.

 

Example 1:Input: 2 Output: true Explanation: Alice chooses 1, and Bob has no more moves.

Example 2:

Input: 3 Output: false Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.

 

Note:

1. 1 <= N <= 1000

2. 소스코드

class Solution(object): 
    def divisorGame(self, N): 
        cnt = 0 
        while N!=1: 
            x = [] 
            for i in range(1,N): 
                if N%i ==0: 
                    x.append(i) 
            N = N -x[0] 
            cnt +=1 
        if cnt%2 ==0: 
            return False 
        else: 
            return True

 

3. 소스코드 설명

Bob과 Alice가 칠판에 적어가며 DivisorGame을 한다.

N이라는 수가 주어지는데, 우리는 0<x<N이면서 N%x ==0인 x 를 찾아야한다.

여기서 x에 해당하는 수는 N의 약수들 중, N를 제외한 것이라고 이해했다.

따라서 for문을 1부터 N 전까지 돌면서, 나누었을 때 0이 되는 수들을 x 리스트에 넣는다.

이 중에서 player가 첫번째 x를 선택하고, 그 선택한 x를 N에서 뺀다.

그 수가 다시 N이 되는 것이므로 N = N -x[0] 라고 써준다.

cnt로는 칠판에 적는 횟수를 카운트할 것인데, 새로운 N이 업데이트 될 때마다 count 해주어야하므로 그 밑에 +1연산자를 써주었다.

Alice가 먼저 게임을 시작하는 것이므로, cnt값이 짝수일 때는 false(패배)를, cnt값이 홀수 일 때는 true(승리)를 반환한다.