LetCode 돌멩이 게임 IV(DP, 최우선 전략 이해)

돌멩이 게임 IV라는 문제를 DP로 해결하는데 관건은'최우수 전략'이 무엇인지 이해하는 데 있다.예를 들어 돌의 개수가 i i i일 때 Alice는 반드시 진다. 그러면 돌의 개수가 i + 1 2, i + 2 2, i + 3 2, i + 4 2,... i + 4 2,... i + 1 ^2, i + 2 ^2, i + 3 ^2, i + 3 ^2, i + 12, i + 22, i + 32, i + 42, i + 42,...... 할 때 Alice가 이기려고 한다면 그는 즉시 그 여분의 완전 제곱수를 가져간다. 그리고 국면은 바로 Bob이 반드시 진다. 왜냐하면 Bob이 시작되기 전의 Alice와 같기 때문이다!
class Solution {
public:
    bool winnerSquareGame(int n) {
        vector<int> dp(n+1);
        dp[0] = 0;
        for(int i=1;i<=n;i++){
            for(int j = 1;j*j<=i;j++){
                if(dp[i]){
                    break;
                }
                dp[i] = !dp[i-j*j] ; 
            }
        }
        return dp[n];
    }
};

다음 표기법은 DP의 점차적인 관계에 더욱 부합된다.
class Solution {
public:
    bool winnerSquareGame(int n) {
        vector<int> dp(n+1,0);
        dp[0] = 0;
        for(int i=0;i<n;i++){
            if(!dp[i]){
                for(int j = 1;j*j+i<=n;j++){
                    dp[j*j+i] = 1;
                }
            }
        }
        return dp[n];
    }
};

좋은 웹페이지 즐겨찾기