[LeetCode] Divisor Game

오늘의 문제는 일종의 숫자 게임의 규칙을 알아내야 하는 문제였다.

leetcode.com/problems/divisor-game/ 

Divisor Game - LeetCode

/*
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.

조건1. 0보다 크고 N보다 작은 x중 N의 약수를 x로 선택한다.
조건2. N을 N-x로 바꾼다.
조건3. N-x가 1이거나 N의 약수가 없다면(무슨수?) 그 사람이 진 것이다.
조건4. 앨리스가 이기면 true를 리턴한다. 두 플레이어가 게임에서 최적의 선택을 했다고 가정한다.
*/

class cote0309_1025_DivisorGame {
    public static boolean divisorGame(int N) {
       if(N%2==0){
           return true;
       }else{
           return false;
       }
    }//속도 0ms, 메모리 35.5 

    public boolean divisorGame2(int N) {
        return (N%2==0)?true:false;  
    }//속도는 둘다 0ms인데 얘가 메모리는 더 많이 나왔다. 35.7. 0.2MB의 차이도 실무에서는 유의미한가?
}

아래는 푼 방법. (좀 이게 맞나 싶긴 한데 일단..)

• 우선 무조건 이기는 수와 무조건 지는 수를 찾았다. (무조건 이김: 2, 무조건 짐: 3)
• 그 다음으로 무조건 이기는 수와 무조건 지는 수를 찾았다. (무조건 이김: 4, 무조건 짐: 5)
• 그 다음으로 무조건 이기는 수와 무조건 지는 수를 찾았다. ... 를 10까지 반복했다. 그랬더니 이기는 수는 짝수, 지는 수는 홀수였다. 그래서 N%2==0으로 리턴값을 결정하는 코드를 돌려보았다. 그랬더니 억셉트 됨..

빛줄기 언니는 이 문제가 수학문제라고 너무 쉬울거라고 했는데 음.. 문과 출신이라 그런지 수능 칠 때 수포자가 아니었음에도 수학을 놓은지 너무 오래 돼서 곧바로 뭐가 생각나진 않았다. 일단 약수, 소수 개념을 떠올려 보고 배스킨라빈스31 게임을 떠올려 보며 둘만 남으면 무조건 이기는 숫자가 있었지.. 라고 생각하며 무조건 이기는 수, 무조건 지는 수를 생각해보았다. 이따가 코테 스터디에서 듣는 이야기가 있으면 추가할 것이다.