[LeetCode] Divisor Game

LeetCode문제 링크

leetcode.com/problems/divisor-game/

Divisor Game - LeetCode

엘리스와 밥이 교대로 게임을하며, 엘리스가 먼저 시작합니다.

 

처음에는 칠판에 숫자 N이 있습니다. 각 플레이어의 차례에 해당 플레이어는 다음과 같이 이동합니다.

 

0 < x < N 이며 N % x == 0인 x를 선택한다.

칠판의 숫자를 N에서 N -x로 바꾼다.

 

둘 중 하나가 이동하지 못하게 되면 게임이 끝난다.

엘리스가 승리했을시 True를 반환하고 밥이 이기면 False를 반환한다.

 

Example 1:

Input: 2 Output: true

설명 : Alice chooses 1, and Bob has no more moves.

Example 2:

Input: 3 Output: false

설명 : Alice chooses 1, Bob chooses 1, and Alice has no more moves. 

 

조건

1 <= N <= 1000

 

testcase

n == 1 -> false

n == 2 -> true

n == 3 -> false

class Solution {
    public boolean divisorGame(int N) {
        int x = 2;

        while(N > 3)
        {
            if(N % x == 0 && N != x)
            {
                N = N - (N / 2);
                x = 2;
            }
            else if(N != x)
            {
                x = x + 1;
                N = N - (N / x);
            }
            else
            {
                x = 1;
                N = N - x;
            }

        }

        if (N == 1) return false;
        if (N == 2) return true;
        if (N == 3) return false;
        return true;
    }
}

임시로 만들어서 돌려본 코드에서 6일 경우 true가 반환되어야 한다고 나온다.

N == 6 -> A3, N3, flag true-> B1 N2 flag false -> A1 N1 flag true -> return true

즉 x값은 가장 큰 약수 값이 되어야 한다는 말이다.

 

class Solution {
   public boolean divisorGame(int N) {
	        boolean flag = false;
	        
	        while(N > 0) // N이 0보다 크다면
	        {
	            for(int x = N-1 ; x > 0; x--)
	            {
	            	System.out.println(x);
	                if(N % x == 0)	// 가장 큰 약수 혹은 1
	                {
	                    N = N - x;	// n을 n-약수
	                    flag = !flag;	// 순서 바꾸기
	                }
	                
	            }
	        }

	        
	        return flag;
	    }
}

 

 

문제이해를 잘 못했던 것 같다.

---

discuss의 문제풀이

devjun.tistory.com/113

Divisor Game - LeetCode (Dynamic Programming)