LeetCode 1025. Divisor Game - DP

leetcode.com/problems/divisor-game/

Divisor Game - LeetCode

 

 

해당 문제는 DP로 풀수 있는 문제.

알고리즘을 안한지 오래되어 차근차근 공부하는 중 DP 관련하여 잘 정리되어있는 블로그가 있어 참고해서 개념 잡았다.

 

velog.io/@nninnnin7?tag=DP

nninnnin7 (justindglee) - velog

 

[풀이]

핵심은 dp[N-x]가 false 이면 dp[N]은 true 라는 것 

 :  dp[N-x]가 false 면 Bob이 이기는 것이고, 여기서 한번 더 기회가 있었다면 Alice가 이긴다는 뜻이기 때문이다.

 

1. Bottom Up 방식 - LeetCode best 솔루션 참고

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

두번째 for문에서 Math.sqrt(i) 까지만을 조건으로한 이유는 뭘까..

 

 

2. Top Down 방식

class Solution {
    int[] dp = new int[1001];
    
    public boolean divisorGame(int N) {
        dp[1]=1;
        int result = cal(N);
        if(result == 2){
            return true;
        }
        return false;
    }
    
    private int cal(int N) {
        if(dp[N]>0) {
            return dp[N];
        }
        
        for(int i=1;i<N;i++){
            if(N%i==0 && (cal(N-i) == 1)) {
                dp[N]=2;
                return dp[N];
            }
        }
        dp[N]=1;
        return dp[N];
    }
    
}