1. 오늘의 문제

Divisor Game

• 출처 : leetcode

2. 문제 분석

• Alice랑 Bob이랑 게임하는데 Alice가 시작함
• 칠판에 n에 해당하는 숫자를 써놓고 시작한다.
• 게임 룰
  • Alice가 먼저 0 < x < n이면서 n % x == 0인 x를 고른다.
  • 칠판에 n - x로 수정한다.
  • 더 이상 수정하지 못할 때까지 반복한다.
• 결과값 : Alice가 이기면 true, Bob이 이기면 false 리턴

• Example 1
  • Input: n = 2
  • Output: true
  • Explanation: Alice chooses 1, and Bob has no more moves.
• Example 2
  • Input: n = 3
  • Output: false
  • Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.

3. 문제 풀이

1. 동적 계획법을 활용해 점화 식 세우기
   • dp[i] : i라는 숫자로 시작할 때 Alice가 승리할 수 있는지 나타냄
   • dp[i]가 'true'이면 i로 시작하는 Alice의 승리
   • dp[i]가 'flase'이면 i로 시작하는 Alice의 패배
2. 만약에 n = 1 이라면, Alice는 x를 고를 수 없어 패배함 ⇾ dp[1] = false

4. 구현 코드

class Solution {
    public boolean divisorGame(int n) {
        // 만약에 n = 1 이라면, Alice는 x를 고를 수 없어 패배
        if (n == 1) {
            return false;
        }

        // 동적 계획법 배열 만들기
        boolean[] dp = new boolean[n+1];
        dp[1] = false;

        // 2부터 n까지의 dp값 계산
        for (int i = 2; i < n + 1; i++) {
            // 각 i에 대해 가능한 x 값 확인
            for (int x = 1; x < i; x++) {
                // i % x는 0이어야 하고 i에서 x를 뺀 값이 false여야
                // Alice가 이기는 거임
                if (i % x == 0 && !dp[i - x]) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
}

5. 오늘의 회고

• 동적 계획법 너무 어렵다... 점화식을 어떻게 세우냐가 문제임..
• 반복하다보면 풀 수 있겠지..?
  

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL