1025. Divisor Game

난이도: Easy

 

문제 설명

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.

 

DP 문제를 풀 때는 항상 전의 값을 어떻게 이용할 수 있을지에 대해서 생각하고 접근해야 한다.

전의 값을 이용해서 다음 값을 구하는 점화식을 만들수 있다면 코드로 구현하는건 어렵지 않다.

 

Top-Down

class Solution {
public:
    int dp[1001] = {0, };
    
    int findWin(int n) {
        if(n == 1)
            return 0;
        
        if(dp[n] != 0)
           return dp[n];   
        else
        {
            dp[n] = findWin(n-1) + 1;
            return dp[n];
        }
    }
    
    bool divisorGame(int N) {
        int result = findWin(N);
        return result % 2 == 0 ? false : true;   
    }
};

 

Bottom-Up

class Solution {
public:
    int dp[1001] = {0, };
   
    bool divisorGame(int N) {
        for(int i=2; i<=N; ++i)
        {
            dp[i] = dp[i-1] + 1;
        }
        
        
        return dp[N] % 2 == 0 ? false : true;
    }
};