[LeetCode] Divisor Game (Dynamic Programming)

약 한시간 가량 풀어봤는데 풀리지 않아서 Discuss답변을 봤습니다.

 

leetcode.com/problems/divisor-game/discuss/979796/Java-all-approach-Easy-Recursive-Memoization-DP

 

문제 이해를 위한 설명

 

• 이 문제는 쉽지만 이해하기 어렵습니다.
• 문제에서 Alice는 1부터 N까지 숫자를 선택할 수 있고, 자신의 승리를 최적화하기 위해 선택합니다. Bob도 마찬가지로 최선을 다합니다.
• 숫자가 2이면 Alice의 순서로 시작하여 1을 선택하고 이깁니다.
• 3일 경우 Alice가 1을 선택하고 밥이 1을 선택하여 앨리스가 집니다.
• 숫자 4일 경우

4 = Alice -> (4-1) - gives 3 to Bob

3 = Bob -> (3-1) - gives 2 to Alice

2 - Alice -> (2-1) - gives 1 to Bob

• 이제 Bob은 아무것도 선택할 수없고
• 이렇게 모든 숫자를 시도하면 N이 홀수라는 것을 알면 앨리스가 지고 , N이 짝수라면 앨리스가 이기는 패턴을 얻게됩니다.
• 이 문제에 대한 간단한 해결책은 N % 2 == 0

O (1) 

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

 

• 이 문제는 재귀함수로도 해결할 수 있습니다.
• N== 1 return false, N == 2 return true
• Alice와 Bob은 1부터 N까지의 숫자 중 하나를 선택할 수 있습니다.
• N % i == 0인 수 중에 최적의 수를 찾습니다.
• 그런 다음 다른 사람에게 남은 번호로 선택권이 제공됩니다.

 

O(N) - Top Down Recursive Solution

class Solution {
   public boolean divisorGame(int N) {

        if (N==1) return false;
        if (N==2) return true;
       
        for (int i=1;i<=N;i++){
            if (N%i == 0)
                return !(divisorGame(N-i));
       }
        return false;
  }
}

 

• 재귀를 사용하면 하위 문제를 반복해서 계산하는 경향이 있습니다.
• 따라서 캐시를 도입하면 이미 계산 된 값을 캐시하는 데 도움이 됩니다.
• 또한 1에서 sqrt (N)까지 반복 할 수 있습니다. 예를 들어 N = 16 인 경우 선택할 수있는 유일한 최적 요인은 다음과 같습니다.

1x16 = 16

2x8 = 16

4x4 = 16

 

O(N) - Recursive with Memoization

 class Solution {
   public boolean divisorGame(int N) {           

        boolean[] cache = new boolean[N+1];
        if (N== 1){
            cache[1] = false;
            return false;
        }
       
        if (N== 2){
            cache[2] = true;
            return true;
        }
       
        for (int i=1;i*i<=N;i++){
            if (N % i == 0){
                cache[i] = !(divisorGame(N-i));
                return cache[i];
            }
        }
        return false;
    }   
 }

 

Bottom up Approach

 

• 상향식 dp 접근 방식을 사용하여이 문제를 해결할 수도 있습니다.
• DP 테이블에 boolean 배열을 N + 1까지 저장
• 1에서 N을 선택하도록 반복합니다.
• j가 각 플레이어가 선택한 숫자를 반복하도록 합니다.
• 승리 한 사람이 있으면 이전 계산 된 값과 함께 현재 값 dp [i]를 저장합니다! dp [i-j]
• 마지막으로 dp [N] 반환

   class Solution {
     public boolean divisorGame(int N) {           
   
       boolean[] dp = new boolean[N+1];
       for(int i=1;i<=N;i++)
        {
            if(i==1) dp[i]=false;
            else if(i==2) dp[i]=true;
            else{
                for(int j=1;j*j<=i;j++)
                {
                    if(i%j==0)
                    {
                       dp[i] = !dp[i-j];
                        break;
                    }
                }    
            }  
        }
        return dp[N];
    }
}