Leetcode Java Can I Win

문제

Link

코드

class Solution {

  public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
    if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) {
      return false;
    } else if (maxChoosableInteger >= desiredTotal) {
      return true;
    } else { 
      return this.dfs(maxChoosableInteger, desiredTotal, new boolean[1 << maxChoosableInteger], 0);
    }
  }

  private boolean dfs(int maxChoosableInteger, int desiredTotal, boolean[] dp, int curr) {
    if (dp[curr]) {
      return dp[curr];
    }
    for (int idx = 0; idx < maxChoosableInteger; idx++) {
      if ((curr & 1 << idx) != 0) {
        continue;
      } else if (idx + 1 >= desiredTotal || !this.dfs(maxChoosableInteger, desiredTotal - idx - 1, dp, curr | 1 << idx)) {
        dp[curr] = true;
        return true;
      }
    }
    return false;
  }

}

결과

Link

설명

1. 두 사람이 아래의 규칙대로 게임을 하여 처음 시작한 사람이 무조건 이기는 게임인지를 검증하는 문제이다.
   • 첫 번째 사람부터 1에서부터 maxChoosableInteger까지 숫자를 골라 번갈아 숫자를 선택한다.
   • 번갈아 고른 수의 합이 desiredTotal 이상 되는 사람이 이긴다.
   • 단, 고른 숫자는 다시 선택할 수 없다.

2. $maxChoosableInteger \times \frac{maxChoosableInteger + 1}{2}$의 결과가 desiredTotal보다 작은 경우 선택 할 수 있는 숫자의 합이 desiredTotal에 미치지 못하므로 둘 다 이길 수 없어, false를 주어진 문제의 결과로 반환한다.

3. maxChoosableInteger이 desiredTotal보다 크거나 같은 경우 처음 시작한 사람이 무조건 이기므로, true를 주어진 문제의 결과로 반환한다.

4. 2, 3번의 경우가 아닌 경우 5번에서 정의한 dfs(int maxChoosableInteger, int desiredTotal, boolean[] dp, int curr) 메서드를 dp에 1의 비트를 좌측으로 maxChoosableInteger번 이동 시킨 크기의 부울 배열을 넣어 수행하여 처음 시작하는 사람이 무조건 이기는지 검증한 결과를 주어진 문제의 결과로 반환한다.

5. DFS 방식으로 처음 시작하는 사람이 이기는지 검증할 dfs(int maxChoosableInteger, int desiredTotal, boolean[] dp, int curr)메서드를 정의한다.
   • dp의 curr번째 값이 true인 경우 처음 시작하는 사람이 이기는지 검증이 되었으므로, true를 반환한다.
   • 0부터 maxChoosableInteger 미만까지 idx를 증가시키며 아래를 반복한다.
     • curr과 1의 AND(&) 비트 연산의 결과를 idx번 좌측으로 이동시킨 결과가 0이 아닌 경우, 무시하고 다음 반복을 수행한다.
     • $idx + 1$이 desiredTotal 이상이거나 desiredTotal 자리에 $desiredTotal - idx - 1$을, curr 자리에 curr과 1의 OR(|) 비트 연산의 결과를 idx번 좌측으로 이동시킨 결과를 넣어 재귀호출을 수행한 결과가 true이면, dp의 curr번째 값을 true로 변경하고 true를 반환한다.
   • 반복이 정상적으로 완료되는 경우 첫 번째 사람이 무조건 이기는 경우가 아니므로, false를 반환한다.

소스

Sample Code는 여기에서 확인 가능합니다.