leetcode 1510 - Stone Game IV

https://leetcode.com/problems/stone-game-iv/

풀이

Alice가 선택할 수 있는 모든 경우를 다 해봐서 이길 수 있는 경우가 하나라도 있으면 그 길을 선택하면 된다. 최소 한 개 이상을 가져가기 때문에 stone이 1개 있는 경우부터 차례대로 n까지 구해간다면 점화식을 세울 수 있다.

 

매 턴이 바뀔 때마다 Alice, Bob 유저가 바뀌므로 d 배열을 정의할 때 선공하는 사람이 최선을 다할 때 이길 수 있는지 여부를 저장해야 한다.

d[i] = i개의 stone이 있을 때 선공하는 사람이 이길 수 있으면 true, 무조건 지면 false

 

이 전 상태를 참조할 때 턴이 바뀌기 때문에 d 배열에 false가 하나라도 있으면 그 길을 선택하는 것이 최선이다.

 

코드

class Solution {
public:
    bool winnerSquareGame(int n) {
        vector<bool> d(n+1);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j*j <= i; j++) {
                if(d[i-j*j] == false) {
                    d[i] = true;
                    break;
                }
            }
        }
        
        return d[n];
    }
};