<Medium> Can I Win (LeetCode : C#)

https://leetcode.com/problems/can-i-win/

📕 문제 설명

최대로 고를 수 있는 숫자와 도달해야할 숫자가 주어질 때 첫 번째 플레이어의 승패 여부 반환하기
(도달해야할 숫자보다 큰 수에 먼저 도달하는 플레이어가 이기며 1~ 최대로 고를 수 있는 숫자 중 겹치지 않는 숫자로 플레이어들은 고를 수 있다.)

• Input
  최대로 고를 수 있는 숫자, 목표 도달 숫자
• Output
  첫 번째 플레이어의 승패 여부

예제

풀이

Memoization이랑 bit mask 엮여있는 문제다. (다음에 다시 풀어봐야 할 듯 하다. 그냥 바로 보고 생각하는게 잘 안되네..)

public class Solution {
    public bool CanIWin(int maxChoosableInteger, int desiredTotal) {
        int sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
        if(sum < desiredTotal) return false;
        if(desiredTotal <= 0) return true;

        return CanIWin(desiredTotal, new Dictionary<int, bool>(), new bool[maxChoosableInteger + 1], 0); 
    }

    private bool CanIWin(int desiredTotal, Dictionary<int, bool> memo, bool[] visited, int state) 
    {
        if(desiredTotal <= 0) return false;   
        if(memo.ContainsKey(state)) return memo[state];

        for(int i = 1; i < visited.Length; i++) // 1 ~ 최대로 고를 수 있는 수 까지 경우 확인해보기
        {
            if(!visited[i]) // 
            {
                visited[i] = true;
                // 1 2 3 4 5 6 7 8 9 10
                // 0 0 0 0 0 0 0 0 0 0
                // 1 을 i 칸만큼 움직여 사용 표시
                if(!CanIWin(desiredTotal - i, memo, visited, 1 << i | state)) // bit 마스킹으로 현재 사용한 숫자 표시한다
                {
                    memo.Add(state, true);
                    visited[i] = false;
                    return true; // 상대편이 내가 현재 낸 값 기준 못 이기는 경우 이므로 return true (!CanIWin 확인함으로써)
                }
                visited[i] = false;
            }   
        } 

        memo.Add(state, false); 
        return false; // 상대방이 이기는 경우 
    }
}

결과