1025. Divisor Game

https://leetcode.com/problems/divisor-game/

 

Discussion 풀이

class Solution {
    public boolean divisorGame(int N) {
        int[] dp = new int[N+1];
        
        dp[0] = -1;
        dp[1] = -1;

        for (int i = 2; i <= N; i++) {
            dp[i] = -1;
            for(int j = 1; j < i; j++) {
                if (i%j == 0 && dp[i - j] == -1) {
                    dp[i] = j;
                }
            }
        } 

        return dp[N] != -1;
    }   
}

class Solution {
public:
    int dp[1005];
    
    bool f(int x, int turn) {
        if(turn == 1 && x == 1) return false; 
        if(turn == 0 && x == 1) return true;
        
        if(dp[x] != -1) return dp[x];
        
        bool ans = false;
        for(int i=1;i<=sqrt(x);i++) {
            if(x % i == 0) {
                ans = ans || f(x - i, !turn);
            }
        }
        
        return dp[x] = ans;
    }
    
    bool divisorGame(int N) {
        memset(dp, -1, sizeof(dp));
        // 1 -> Alice
        return f(N, 1);
    }
};

 

 

O 풀이

dp 풀이

class Solution {
   int dp[1001];
public:
   bool divisorGame(int n) {
      // dp[n]. n is number, not Index
      dp[1] = 0; 
      dp[2] = 1;
      for( int i = 3; i <= n; i++ )
      {
         dp[i] = 0;
         for( int j = i - 1; j >= 1; j-- ) //x 범위
         {
            if( i % j != 0 ) //x의 조건
               continue;

            if( dp[i - j] == 0 ) //다음 턴에 상대가 죽는지 체크
            {
               dp[i] = j;
               break;
            }         
         }
      }

      //return dp[n]; //다음 턴에 상대가 죽는 최대 값.
      return dp[n] != 0;
   }
};

class Solution {
public:
    bool divisorGame(int N) {
        return N % 2 == 0;
    }
};

 

D 풀이

DP 문제인지모르겠음 -0-

class Solution {
public:
    bool divisorGame(int N) {
        return !(N & 1);
    }
};