[LeetCode | Java | 동적 계획법 문제 풀이] 1025. Divisor Game - Solution with Brainteaser

99 Club 2기 | Java | Beginner

➗ 1025. Divisor Game

🏷 관련 주제 : Math Dynamic Programming Brainteaser Game Theory

Easy

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there is a number n on the chalkboard.

On each player's turn, that player makes a move consisting of:

• Choosing any x with 0 < x < n and n % x == 0.
• Replacing the number n on the chalkboard with n - x.

Also, if a player cannot make a move, they lose the game.

Return true if and only if Alice wins the game, assuming both players play optimally.

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.

Constraints:

1 <= n <= 1000

Accepted    258.3K  |  Submissions    375.2K  |  Acceptance Rate    68.8%

---

✔ Solution with Brainteaser🧠

class Solution {
    public boolean divisorGame(int n) {
        boolean answer = true;

        if (n % 2 == 1) {
            answer = false;
        }

        return answer;
    }
}

채점 결과

💥 오늘 만난 문제 & 나의 시도 💦 & 해결 방법 👍

📌 오늘 만난 문제

엘리스가 밥과 게임을 할 때, 순서는 한번씩 번갈아 가며 바뀐다.
자연수 n이 주어지면 해당 턴의 플레이어는 다음의 규칙을 만족하는 자연수 x를 찾아 n을 n - x로 바꾸어 놓는다.

• 0 < x < n
• n % x == 0

엘리스와 밥은 이기기 위해 항상 최선의 선택을 한다. 엘리스가 이기는 경우에만 boolean divisorGame(int n)이 false를 반환한다.

---

처음에는 재귀함수로 구하려고 했는데
테스트 케이스에서는 잘 동작했지만 코드를 제출했을 때, 계속 런타임 아웃이 떠서
노트에 경우의 수를 생각하며 규칙을 찾다가
잘은 모르겠지만 엘리스가 짝수일 때만 계속 승리하는 것 같아서
매개변수 n이 홀수일 때만 false를 반환하도록 코드를 고쳐서 제출했는데 성공이 떴다.😲🍀
이유를 알지 못하고 맞을 수는 없으니 문제를 다시 분석해 보았다.

---

🤔❓ n = 1부터 반환값 및 승패가 어떻게 되는지 알아보자.

 

n = 1

• 0 < x < 1을 만족하는 자연수 x가 존재하지 않는다.
• 엘리스 패배 : false 반환 (밥 승리)

1을 받는 사람은 패배한다.

n = 2

• 엘리스는 이기기 위해 최선을 다한다.
• 밥이 받는 숫자를 1로 만든다.
• 엘리스가 1을 골라 2를 2 - 1 = 1로 바꾼다.
• 1은 0 < 1 < 2이고 2 % 1 == 0이다.
• 엘리스 승리 : true반환 (밥 패배)

2를 받는 사람은 승리한다.

n = 3

• 엘리스가 고를 수 있는 수는 1밖에 없다.
• 밥은 2를 받는다.
• 엘리스 패배 : false 반환 (밥 승리)

3을 받는 사람은 패배한다.

n = 4

• 엘리스가 고를 수 있는 수는 1, 2
• 1을 고르면 밥이 3을 받는다.
• 엘리스 승리 : true 반환 (밥 패배)

4를 받는 사람은 승리한다.
...

---

받는 수에 따른 승패

• 1, 3, ... : 패배
• 2, 4, ... : 승리

🤓❗ 혹시 홀수를 받으면 패배, 짝수를 받으면 승리인 것일까?

홀수를 받아 승리하려면, 상대에게 다시 홀수를 주어야 한다.

홀수 - x == 홀수이려면
x는 짝수이어야 한다.
(왜냐하면, 홀 - 홀 = 짝/ 홀 - 짝 = 홀)

 

그런데 홀수 % 짝수 == 1
즉, 홀수 % 짝수 != 0

 

그러므로

• 0 < x < n
• n % x == 0 (여기를 만족하지 않음)
• n은 홀수
• n - x는 홀수

를 만족하는 x는 존재하지 않는다.

즉, 홀수를 받으면 패배 💩

 

짝수를 받았을 때, 1을 고르면
상대 플레이어에게 무조건 홀수를 주게되므로 승리한다.
즉, 짝수를 받으면 승리 🏆

---

1. 반환할 논리값 변수 boolean answer 초기화

  boolean answer = true;

 

2. boolean divisorGame(int n)의 매개변수 n이 홀수이면 false를 반환하고
n이 짝수이면 true를 반환하자.

초기값이 true이므로 n이 홀수일 때만 answer에 false를 할당하자.

 

  if (n % 2 == 1) {
      answer = false;
  }

 

3. answer에 할당된 값을 반환하자.

  return answer;

💬 무엇을 새롭게 알았는지

열심히 경우의 수를 생각해 보며 노트에 써보고 거기서 찾은 규칙을 찾아 코드를 써 보는 경험을 할 수 있었다.

---

📚 References(참고 자료)

• [LeetCode | Java | 내가 올린 풀이] Solution is simple