99클럽(2기) - 코테스터디 12일차 TIL # Dynamic Programming

 

LeetCode - 1025. Divisor Game

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.

---

 

풀이

음? n이 짝수이면 항상 이기고 n이 홀수이면 항상 지는 거 아니가? n이 짝수이면 Alice가 항상 x = 1을 선택하면 되고, n이 홀수이면 항상 Bob이 항상 x = 1을 선택할 수 있는 상황이다.

1) n이 짝수인지 판별한다.

class Solution:
    def divisionGame(self, n) -> bool:
        return n % 2 == 0

 

느낀점

DP는 전략을 잘 짜면 엄청 쉽게 풀 수 있는 것 같다.